Solution: Swapping Nodes in a Linked List

Let's solve the Swapping Nodes in a Linked List problem using the In-Place Manipulation of a Linked List pattern.

We'll cover the following

Statement

Given the linked list and an integer, k, return the head of the linked list after swapping the values of the kthk^{th} node from the beginning and the kthk^{th} node from the end of the linked list.

Note: We’ll number the nodes of the linked list starting from 11 to nn.

Constraints:

  • The linked list will have n number of nodes.
  • 1≤1 \leq k ≤\leq n ≤500\leq 500
  • −5000≤-5000 \leq Node.value ≤5000\leq 5000

Pattern: In-place Manipulation of a Linked List

We need to find the kthk^{th} node from the start of the linked list and the kthk^{th} node from the end of the linked list. We find the two nodes in the linked list using the in-place manipulation method. We use two pointers to traverse the linked list to find the kthk^{th} node from the start and the kthk^{th} node from the end of the linked list.

Once we’ve found these nodes, we swap their values without changing their positions.

Solution

There are multiple approaches to solving this problem: the three-pass, two-pass, and one-pass approaches. An efficient approach using a one-pass solution enables the swapping of kthk^{th} node from both ends of a linked list without determining the length of the list. The method involves advancing two pointers, curr and end, through the list, maintaining a gap of kk nodes between them. Initially, both pointers start from the head, with curr moving kk steps ahead. When the curr pointer reaches the kthk^{th} node, the end pointer starts moving from the head, while we use another pointer, front, to store the current position of curr. It continues the traversal by moving both curr and end pointers one step ahead until the curr reaches the end of the list. This ensures that the end pointer points the kthk^{th} node from the end of the list upon completing the traversal. The final step involves swapping the nodes pointed by the front and end pointers, effectively swapping the positions of the kthk^{th} nodes from both ends.

Now, let’s look at the different approaches to solving the problem.

The three-pass approach:

Let’s use two pointers, front and end, to help traverse a linked list and find the kthk^{th} node at the start and end of the linked list:

  • First pass: To find the kthk^{th} node at the start of the linked list, we traverse the linked list from the head to the kthk^{th} node using the front pointer.

To find the kthk^{th} node at the end of the linked list, we need to traverse the linked list two times.

  • Second pass: We must find the length of the linked list to find the exact position of the end node. We traverse the linked list from the head to the last node to find the length of the linked list.
  • Third pass: The kthk^{th} node from the end will be located at the (length−k)th(length−k)^{th} position from the start. Therefore, we traverse the linked list again from the head to the (length−k)th(length−k)^{th} node to find the kthk^{th} last node.

After finding the front and end nodes, we can swap the values of the nodes.

The two-pass approach:

We can optimize the approach above by finding the front node (the kthk^{th} node from the start) and the length of the linked list in a single pass, and then finding the end node (the kthk^{th} node from the end) in another pass.

Now, let’s try to solve the problem in a single pass.

The one-pass approach:

In the two-pass approach, before finding the end node (the kthk^{th} node from the end), we first need to find the length of the linked list by traversing the complete list. We can optimize this by finding the end node without calculating the length of the linked list. We traverse the linked list using two pointers, end and curr, by keeping the end pointer k positions behind the curr pointer. When the curr pointer reaches the last node, the end pointer is at the kthk^{th} last node.

Let’s look at the algorithm of the approach discussed above:

  • Initialize the count variable with 00.
  • Set the front and end pointers to NULL and the curr pointer to the head node.
  • Traverse the linked list using the curr pointer and increment count on every step.
  • When count becomes equal to k, it means that we’ve reached kthk^{th} node from the start. At this point, we perform the following two steps:
    • We set the front pointer to curr node.
    • We set the end pointer to the head node. After doing this, the end node is exactly kk nodes behind the curr node.
  • We continue traversing the linked list, but along with the curr pointer, we move the end pointer too.
  • When curr reaches the end of the linked list, the end pointer will be pointing to the kthk^{th} node from the end of the linked list.
  • We swap the values of the front and end nodes and return the head of the linked list.

Let’s look at the following slides to get a better understanding of the steps:

Let’s implement the algorithm as discussed above:

main.java
LinkedListNode.java
LinkedList.java
PrintList.java
class SwapNodes {
    public static void swap(LinkedListNode node1, LinkedListNode node2) {
        int temp = node1.data;
        node1.data = node2.data;
        node2.data = temp;
    }
    public static LinkedListNode swapNodes(LinkedListNode head, int k) {
        if (head == null) {
            return head;
        }
        int count = 0;
        LinkedListNode front = null;
        LinkedListNode end = null;
        LinkedListNode curr = head;
        while (curr != null) {
            count += 1;
            if (end != null) {
                end = end.next;
            }
            if (count == k) {
                front = curr;
                end = head;
            }
            curr = curr.next;
        }
        swap(front, end);
        return head;
    }
    public static void main(String[] args) {
       
        int[][] input = {
            {1, 2, 3, 4, 5, 6, 7},
            {6, 9, 3, 10, 7, 4, 6},
            {6, 9, 3, 4},
            {6, 2, 3, 6, 9},
            {6, 2}
        };
        int[] k = {
            2, 3, 2, 3, 1
        };
        for(int i=0; i<input.length; i++){
            System.out.print(i+1);
            LinkedList<Integer> list = new LinkedList<Integer>();
            list.createLinkedList(input[i]);
            System.out.print(".\tOriginal linked list is: ");
            PrintList.printListWithForwardArrow(list.head);
            System.out.println("\tk: "+k[i]);
            System.out.print("\tLinked list with swapped values: ");
            PrintList.printListWithForwardArrow(swapNodes(list.head,k[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Swapping Nodes in a Linked List

Solution summary

Let’s summarize the steps we performed to solve the problem:

  • Initialize a count variable with 00, the front and end pointers with NULL, and point the curr pointer to the head of the linked list.
  • Iterate the linked list using curr, and increment the count variable at each step.
  • When count becomes equal to kk, set front equal to the curr pointer and move the end pointer to the head.
  • Continue moving the end and curr pointers forward until curr reaches the last node.
  • Swap the values of these front and end nodes.

Time complexity

The time complexity of this solution is O(n)O(n), where nn is the number of nodes in the linked list.

Space complexity

The space complexity of the solution is O(1)O(1).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.