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 in a linked list.

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: changing the node pointers
• Recursive approach : changing the node pointers
• Iterative approach : swapping the values of the nodes
• Recursive approach : swapping the values of the nodes

Iterative approach: changing the node 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, we 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

We define a function pairWiseSwap(ListNode head), which takes the head of the linked list as input and returns the head pointer of the pair-wise swapped linked list.

1. If the linked list is empty or there is a single node, we return the head as an output, i.e., if (head == NULL || head->next == NULL), return head. Otherwise, we move forward in a loop to pick nodes in pairs and swap their links.

2. Before starting the loop:

   • We need to define the head of the modified linked list, which will be the second node from the start i.e. newHead = head->next.
   • We initialize a loop pointer currNode with the head node to track the pair of nodes i.e. current and next node in the linked list. currNode = head
3. Now we run a loop to swap list nodes in pairs by changing links. What will be the loop condition? The idea is simple: we are considering two nodes simultaneously, so we run loop till currNode and currNode->next are not NULL. Now we perform the pointers swapping.
4. Before exchanging the links, we save the start node of the next pair in a temporary pointer. temp = curr->next->next.
5. Now we update the pointer currNode->next->next to the current node i.e. currNode->next->next = currNode.
6. Then we set the pointer currNode->next to the starting node of the next pair i.e. temp node. currNode->next = temp.
7. Finally, before moving to the next iteration of pairwise swapping, we update the current node with the first node of the next pair i.e. currNode = temp.
8. By the end of the loop, we return newHead as the output.

Solution Pseudocode

ListNode pairWiseSwap(ListNode head)
{ 
    if (head == NULL || head->next == NULL) 
        return head
    ListNode currNode = head
    ListNode newHead = head->next
    while (currNode != NULL && currNode->next != NULL) 
    {
        ListNode temp = currNode->next->next
        currNode->next->next = currNode
        currNode->next = temp
        currNode = temp
    }
    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).

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? 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 basic solution idea would be: 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 remaining linked list of size n-2 recursively.

Solution Steps

1. Base case: This is a situation when there is a single node or no node in the linked list. if (head == NULL || head->next == NULL), return head.

2. Now, we swap the first pair of nodes i.e. head and head->next.

   • We first save the head of the remaining list in a pointer variable for the input parameter of the recursive call i.e. remainingListHead = head->next->next.
   • We update the new head pointer of the modified linked list, which would be the head->next. newHead = head->next.
   • Finally, we update the newHead next pointer with the head node. newHead->next = head
3. After swapping the first two nodes, we call the same function to swap the remaining linked list with remaingListHead as the input parameter. This function returns the head of the remaining modified linked list, which would be the next pointer of the head node. head->next = pairWiseSwap(remainingListHead). Think!
4. Finally, we return newHead as an output.

Solution Pseudocode 

ListNode pairWiseSwap(ListNode head) 
{
    if (head == NULL || head->next == NULL)
        return head
    ListNode remainingListHead = head->next->next
    ListNode 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 function T(n) = T(n-2) + O(1), where base case is the situation of T(1) = c and T(0) = c.
• The basic analysis of the above recurrence is very simple: our recursion will terminate at base case after n/2 number of steps. Why? because at each step, the input size is decreasing by 2! Think! So time complexity = n/2*O(1) = O(n). Explore this blog to understand recursion analysis: Analysis of Recursion.
• The space complexity depends on the size of the recursion 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). Think!

Iterative approach : swapping the values of the nodes

Solution Idea

Another basic idea to solve this problem is by swapping node values in pairs instead of changing pointers. The solution begins with the first node and keeps swapping values in pairs till we reach the NULL node. Here we swap the data of the nodes keeping their addresses as it is.

Efficiency note: If data contains too many fields, then we need to perform several swap operations. So swapping links is an efficient idea in comparison to swapping values! Think!

Solution Steps

• Create a temporary variable and assign it to the head node. temp = head
• Now we run a loop till temp != NULL && temp->next != NULL

• At each step of the iteration, we swap the value of one pair of nodes and move to temp->next->next if it exists.

  swap(temp->data, temp->next->data)
  temp = temp->next->next

• By the end of the loop, we return the head pointer.

Solution Pseudocode

ListNode pairWiseSwap(ListNode head) 
{ 
    if (head == NULL||head->next == NULL)
        return head
    ListNode temp = head
    while (temp != NULL && temp->next != NULL)
    { 
        swap(temp->data, temp->next->data)
        temp = temp->next->next
    }
    retun head
}

Solution analysis

We are doing a single traversal of the linked list and performing data swapping operations at each iteration. Suppose we have m data fields in a linked list node, then we need to swap each data field for each pair of nodes. In other words, we need to perform O(m) data swapping operations for each node during the swapping operation.

If the total number of nodes is n, time complexity = Time complexity of data swapping for each pair of nodes * total number of node pairs = O(m) * n/2 = O(mn)

• If m is constant then time complexity = O(n)
• If m ~ n, then time complexity = O(n^2)

We are using constant extra space, so space complexity = O(1)

Recursive approach : swapping the values of the nodes

We can also think to implement the above approach recursively. If there are 2 or more than 2 nodes in the linked list then we swap the first two nodes and recursively swap pair-wise nodes for the remaining linked list. Think!

Recursive structure: pairWiseSwap(head) = swap(head->data, head->next->data) + pairWiseSwap(head->next->next)

Base case: if ( head == NULL || head->next == NULL), return head.

Solution Pseudocode

ListNode pairWiseSwap(ListNode head)
{
    if (head == NULL || head->next == NULL) 
        return head
    else    
    {
        swap(head->data, head->next->data)
        pairWiseSwap(head->next->next)
        return head
    }
}

Solution analysis

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

• Here at each step of recursion, we are swapping data of one pair of nodes. In other words, our input size will decrease by 2 at each step of recursion.
• Suppose there are m data fields in a linked list node, so we need to perform O(m) data swapping operations at each step of recursion.
• So time complexity function T(n) = T(n-2) + O(m), where base case is the situation of T(1) = c and T(0) = c.
• The basic analysis of the above recurrence is very simple: our recursion will terminate at base case after n/2 number of steps. Why? because at each step, the input size is decreasing by 2! Think! So time complexity = n/2*O(m) = O(nm).
• If m is constant then the time complexity = O(n), If m ~ n, then time complexity = O(n^2).

The space complexity depends on the size of the recursion 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. For this, the size of the call stack would be O(n), so space complexity = O(n)

Critical ideas to think!

• What would be the solution approach if a doubly-linked list is given instead of a singly linked list?
• How do we implement the swap operation in the last two approaches?
• A dummy node is often used in linked list questions to avoid a special case at the beginning of the list. How can we apply the dummy node idea in this problem?
• How can we use the double-pointer (pointer to pointer) to solve this problem, so we do not need to update the head pointer during swap separately?
• This problem is a special case of "reverse every k node of a linked list" with k = 2. Think!
• How can we modify the above iterative solutions to solve this problem using two pointers: "prev" and "curr"?
• Can we think to solve the recursive solution of changing links by recursively doing pair-wise swapping of the remaining list of size n-2 and then swapping the links of the first two nodes?
• Why swapping link solution is better in comparison to the swapping data?

Suggested coding questions to practice

• Remove nth node from list end
• The intersection of two sorted linked lists
• Find the middle node of a linked list
• Reversing a linked list
• Detect loop in a linked list
• Check if a linked list is pairwise sorted
• Reverse nodes in k-group
• Swap Kth node from beginning with Kth node from the end in a linked list
• Reverse even elements in a linked list
• Move last m elements to the front of a given linked list
• Check if elements of the linked list are present in pair

Enjoy learning, Enjoy coding, Enjoy algorithms!