Swap Linked List Nodes in Pairs

Difficulty: Medium, Asked-in: Facebook, Microsoft, Amazon, Adobe, Yahoo.

Key takeaway: An excellent problem to learn problem-solving using iteration and recursion.

Let’s understand the problem!

Given a singly linked list, write a program to swap every two adjacent nodes and return its head. If the number of nodes is odd, then we need to pair-wise swap all the elements except the last element.

Examples

Input: 12->42->9->30->56->20->NULL

Output: 42->12->30->9->20->56->NULL

Input: 1->2->3->4->5->NULL 

Output: 2->1->4->3->5->NULL

Discussed solution approaches

  • Iterative approach by changing the pointers (Two-pointers)
  • Iterative approach by changing the pointers (Three-pointers using dummy node)
  • Recursive approach  by changing the node pointers
  • Iterative approach  by swapping node values
  • Recursive approach  by swapping node values

Iterative approach by changing the pointers

Solution Idea

The idea is to traverse the linked list linearly, pick the nodes in pairs and swap their links. By the end of the process, return the head pointer of the modified list. The idea looks simple, but we need to be careful with the pointer's movement.

Solution Steps

Step 1: If the list is empty or contains only one node, no swaps are needed. We return head. Otherwise, proceed with pairwise swapping.

Step 2: After the first swap, the second node becomes the new head. We set newHead = head->next. Initialise curr = head and prev = NULL.

Step 3: While curr and curr->next are not NULL, we swap the adjacent pair:

  • Identify the first node: first = curr.
  • Identify the second node: second = curr->next.
  • Link first to the node after the pair: first->next = second->next.
  • Link second to first: second->next = first.
  • Connect the previous pair to the current pair: if prev != NULL, set prev->next = second.
  • Update prev = first to maintain the connection with the next pair.
  • Move curr forward: curr = first->next.

Step 4: After completing all pairwise swaps, return newHead.

Key observation: The prev pointer maintains the connection between consecutive swapped pairs.

Solution pseudocode

pairWiseSwap(head)
    if head == NULL OR head -> next == NULL
        return head

    curr = head
    newHead = head -> next
    prev = NULL

    while curr != NULL AND curr -> next != NULL
        first = curr
        second = curr -> next

        first -> next = second -> next
        second -> next = first

        if prev != NULL
            prev -> next = second

        prev = first
        curr = first -> next

    return newHead

Solution Analysis

We are doing a single traversal of the linked list and performing pointer movement operations at each iteration. In other words, we are doing constant operations with each node in the linked list. So, time complexity = O(n), where n is the number of nodes. We are using constant extra space, so space complexity = O(1).

Iterative approach by changing the pointers (using dummy node)

Here is another approach that uses a dummy node. The dummy node simplifies pointer initialisation and makes it easier to handle changes to the head of the list. Let’s see how this works.

If we keep track of the node before each pair, we can swap pairs iteratively. We use three pointers: prev points to the node before the pair, while first and second point to the two nodes being swapped. After swapping them, we update the pointers to move on to the next pair.

Here are the steps:

  1. We create a dummy node and set its next pointer to the original head of the list. We then initialise a pointer, prev, with the dummy node. The goal of this pointer is to keep track of the node before the pair currently being swapped.
  2. We iterate through the list as long as there are at least two nodes after prev. Inside the loop, we define two pointers, first and second, and assign them to the nodes to be swapped, i.e., the current node and the next node.
  3. Now, we perform the actual swapping. We set prev->next to second, first->next to second->next, and second->next to first. This completes the swap. After that, we move prev to the previous node of the next pair, i.e., first.
  4. By the end of the loop, we return the new head, i.e., dummy->next.

Solution pseudocode

pairWiseSwap(head)
    dummy = new ListNode(0)
    dummy -> next = head
    prev = dummy

    while prev -> next != NULL AND prev -> next -> next != NULL
        first = prev -> next
        second = prev -> next -> next
        // Swapping nodes
        prev -> next = second
        first -> next = second -> next
        second -> next = first
        // Move to the next pair
        prev = first

    head = dummy -> next
    delete dummy

    return head

Solution Analysis

We are doing a single traversal of the linked list. So, time complexity = O(n), where n is the number of nodes. We are using constant extra space, so space complexity = O(1).

Recursive approach : changing the node pointers

Solution Idea

Now a critical question is: Can we solve this problem using the solution of a smaller sub-problem i.e. using recursion? If yes, then what would be the recursive structure? Let's think!

Suppose there are n nodes in the linked list and we swap the first two nodes. Now the problem will get reduced to swapping the remaining n - 2 nodes in pairs. So the solution idea would be to swap the first two nodes and call the same function for the remaining list if there are more than two nodes in the list. By the end of the process, we should return the head of the modified linked list.

Recursive structure: Pair-wise swapping of linked list size of n = Swapping the first two nodes + Pair-wise swapping of the remaining linked list of size n - 2 recursively.

Solution Steps

Base case: This occurs when the linked list contains a single node or no nodes. In this case, if (head == NULL || head->next == NULL), return head.

  1. Now, we swap the first pair of nodes, i.e., head and head->next.
  2. First, we save the head of the remaining list in a pointer variable, which will be used as the input parameter for the recursive call: remainingListHead = head->next->next.
  3. We update the new head of the modified linked list: newHead = head->next.
  4. Finally, we update the next pointer of newHead to point to the head node: newHead->next = head.
  5. After swapping the first two nodes, we call the same function to swap the remaining linked list, passing remainingListHead as the input parameter. This function returns the head of the modified remaining linked list, which becomes the next pointer of the head node: head->next = pairWiseSwap(remainingListHead). Think!
  6. Finally, we return newHead as the output.

Solution pseudocode

pairWiseSwap(head)
    if head == NULL OR head -> next == NULL
        return head

    remainingListHead = head -> next -> next
    newHead = head -> next

    newHead -> next = head
    head -> next = pairWiseSwap(remainingListHead)

    return newHead

Solution Analysis

Suppose the total number of nodes in the linked list is n.

  • At each step of recursion, we are swapping one pair of nodes. In other words, our input size will decrease by 2 at each step of recursion.
  • We are performing O(1) or constant operations at each step of recursion.
  • So time complexity T(n) = T(n-2) + O(1), where the base case is T(1) = c and T(0) = c.
  • The basic analysis of the above recurrence is very simple: Recursion will terminate at base case after n/2 number of steps. Why? Because at each step, the input size is decreasing by 2. So time complexity = n/2*O(1) = O(n).

The space complexity depends on the size of the call stack which will be equal to the height of the recursion tree. There would be a total n/2 number of recursive calls till our recursion reach the base case, so the height of the recursion tree = n/2. For this, recursion will use a call stack of size n/2, so space complexity = O(n).

Suggested coding questions to practice

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com.Enjoy learning, Enjoy coding, Enjoy algorithms!

Find us on:

Self-paced Courses and Blogs