Swap Nodes in Pairs Problem (C++, Java, Python)

Linked List is the most important topic that is asked in interviews and students find it a bit difficult than other data structures. One of them is reversing a linked list, and finding the even position elements. In this article, we will discuss the Swap Nodes in Pairs problem, which is based on a linked list.

Swap Nodes in Pairs Problem Explained

In the Swap Nodes in Pairs problem, you are given a linked list. You have to return the list by swapping every two adjacent elements. Let’s understand this with an example.

As we can see after swapping the adjacent elements we will get the resultant list.

Brute Force Approach

The brute force approach to solve this problem is to store all the values of the linked list in an array. Now iterate over the array and swap every two adjacent elements. Now again from the linked list from the given array. The resultant list will be our answer.

Let’s examine this approach step by step:

1. First, create a vector v. 
2. Iterate over the given linked list and store the values of the list in the array.
3. Swap the adjacent pairs.
4. Now for the new linked list from the given array.

The time complexity for the above code is O(n) where n is the total number of nodes in the linked list. The space complexity is O(n) as we are storing the values in the array whose size will be the same as the total number of nodes.

Iterative Approach

In the above approach, we are storing values in the array, which increases our time complexity from O(1) to O(n). In this approach, we will iterate over the linked list, swap the adjacent pairs at the same time, and move to the next node. 

We first iterate over the list and swap the pairs if they exit. Then, move to the next to next node and repeat the same process until we reach the NULL node or reach the last node.

The time complexity for the above approach is O(n) as we are iterating over the whole linked list. The space complexity is O(1) as we are not using extra space to store the values of the linked list.

Recursive Approach

The above approach can also be solved recursively. Find out the differences between iteration and recursion here.

We can Recursively call the reverse function for the next-to-next node of the current node, swap the current node and the node adjacent to it, and add the recursively returned list to the node next to the current one.

Let’s examine the step-by-step approach:

1. First, check if we are at the last node or null node then return the current node.
2. Now recursively call function for next to next node and store the value in temp node.
3. Swap the current node and the node next to it. Made the next pointer point to the temp address.
4. Return the updated list.

Let’s now come down to writing the code.

C++ Code

Here is the C++ program to Swap Nodes in Pairs for Linked List:

#include<bits/stdc++.h>
using namespace std;

class node{
    public:
    int data;
    node* next;

    node(int x){
        data = x;
        next = NULL;
    }
};

node* swap_pair(node* head){
    if(head == NULL || head->next == NULL) return head;

    node* temp = swap_pair(head->next->next);
    node* temp1 = head->next;
    head->next->next = head;
    head->next = temp;
    head = temp1;
    return head;
}

int main(){

    node* head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);

    head = swap_pair(head);

    // print the linked list
    while(head){
        cout<<head->data<<" ";
        head = head->next;
    }
    return 0;
}

Java Code 

We can implement it in Java also:

class Node {
    int data;
    Node next;

    Node(int x) {
        data = x;
        next = null;
    }
}

public class Main {
    static Node swapPair(Node head) {
        if (head == null || head.next == null) return head;

        Node temp = swapPair(head.next.next);
        Node temp1 = head.next;
        head.next.next = head;
        head.next = temp;
        head = temp1;
        return head;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);

        head = swapPair(head);

        // print the linked list
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
}

Python Code

You can even use Python to implement the recursive approach:

class Node:
    def __init__(self, x):
        self.data = x
        self.next = None

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

    temp = swap_pair(head.next.next)
    temp1 = head.next
    head.next.next = head
    head.next = temp
    head = temp1
    return head

if __name__ == "__main__":
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    head.next.next.next = Node(4)

    head = swap_pair(head)

    # print the linked list
    while head:
        print(head.data, end=" ")
        head = head.next

Output: 

2 1 4 3

The time complexity for the recursive approach to solve Swap Nodes in Pairs problem is O(n) since we are traversing each node of the linked list. The space complexity is O(1) as we are not utilizing any additional space.

Here is a comparison of all the approaches:

Conclusion

In this article, we have seen various approaches to solve the leetcode problem of Swap Nodes in Pairs for a Linked List with implementation in C++, Java, and Python. This is a very interesting question that was asked in many technical interviews. We had seen how we approach the problem recursively and iteratively. We also compared the time complexity of both approaches.