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

Iterative approach by 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.

Step 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.

Step 2: Before starting the loop:

• We 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.

Step 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 the loop till currNode and currNode->next are not NULL. Now we perform the pointers swapping inside the while loop.

1. We create a temporary pointer, temp, and assign it to currNode->next. This will help us to store the next node temporarily.
2. We then update currNode->next to skip the next node and directly point to the node after it (currNode->next = currNode->next->next). This will effectively remove the next node from its current position.
3. Now we swap the positions of currNode and temp by setting temp->next to currNode.
4. We move the currNode pointer to the next position (currNode = currNode->next) to continue traversing the linked list.
5. If currNode and its adjacent node are both not NULL, we update the temp->next->next pointer to point to the next node after currNode. This step will ensure that the swapped nodes are correctly linked to the rest of the list.

Step 4: After the completion of the while loop, we have completed the pairwise swapping, and the newHead pointer points to the correct head of the modified linked list. So we return newHead.

The overall idea is to use two pointers (currNode and temp) to perform the pairwise swapping and update the necessary pointers at each step to ensure the correct connections between nodes.

Solution Code C++

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;
        currNode->next = currNode->next->next;
        temp->next = currNode;
        currNode = currNode->next;
        if (currNode != NULL && currNode->next != NULL)
            temp->next->next = currNode->next;
    }
    
    return newHead;
}

Solution Code Python

def pairWiseSwap(head):
    if head is None or head.next is None:
        return head

    currNode = head
    newHead = head.next

    while currNode is not None and currNode.next is not None:
        temp = currNode.next
        currNode.next = currNode.next.next
        temp.next = currNode
        currNode = currNode.next
        if currNode is not None and currNode.next is not None:
            temp.next.next = currNode.next

    return newHead

Solution Code Java

class PairwiseSwapLinkedList 
{
    public static 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;
            currNode.next = currNode.next.next;
            temp.next = currNode;
            currNode = currNode.next;
            if (currNode != null && currNode.next != null)
                temp.next.next = currNode.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).

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

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 Code C++

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 Code Python

def pairWiseSwap(head):
    if head is None or head.next is None:
        return head

    remainingListHead = head.next.next
    newHead = head.next
    newHead.next = head
    head.next = pairWiseSwap(remainingListHead)
    return newHead

Solution Code Java

public class PairwiseSwapLinkedList 
{
    public static 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 the base case is the situation of 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). Explore this blog to understand the concept of 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

We can solve this problem using another idea: 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 i.e. temp = head.
• Now we run a loop till temp != NULL && temp->next != NULL.
• At each step of iteration, we swap the value of one pair of nodes and move to temp->next->next.
• By the end of the loop, we return the head pointer.

Solution Code C++

ListNode* pairWiseSwap(ListNode* head) 
{
    if (head == NULL || head->next == NULL)
        return head;

    ListNode* temp = head;
    while (temp != NULL && temp->next != NULL) 
    {
        swap(temp->val, temp->next->val);
        temp = temp->next->next;
    }

    return head;
}

Solution Code Python

def pairWiseSwap(head):
    if head is None or head.next is None:
        return head

    temp = head
    while temp is not None and temp.next is not None:
        temp.val, temp.next.val = temp.next.val, temp.val
        temp = temp.next.next

    return head

Solution Code Java

public class PairwiseSwapLinkedList 
{
    public static ListNode pairWiseSwap(ListNode head) 
    {
        if (head == null || head.next == null)
            return head;

        ListNode temp = head;
        while (temp != null && temp.next != null) 
        {
            int tempVal = temp.val;
            temp.val = temp.next.val;
            temp.next.val = tempVal;
            temp = temp.next.next;
        }

        return 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.

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 Code C++

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

Solution Code Python

def pairWiseSwap(head):
    if head is None or head.next is None:
        return head

    head.val, head.next.val = head.next.val, head.val
    pairWiseSwap(head.next.next)

    return head

Solution Code Java

public class PairwiseSwapLinkedList 
{
    public static ListNode pairWiseSwap(ListNode head) 
    {
        if (head == null || head.next == null)
            return head;
        else 
        {
            int tempVal = head.val;
            head.val = head.next.val;
            head.next.val = tempVal;
            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.
• 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: 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(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?
• 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 to 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 separately during the swap?
• This problem is a special case of "reverse every k nodes of a linked list" with k = 2. Think about it!
• How can we modify the above iterative solutions to solve this problem using two pointers: "prev" and "curr"?
• Can we think of solving the recursive solution by recursively performing pair-wise swapping of the remaining list of size n-2 and then swapping the links of the first two nodes?
• Why is the solution involving swapping links better compared to 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
• 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

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