The goal of this problem is to swap nodes of a given linked list in pairs, that is, swapping every two adjacent nodes. If we are allowed to swap just the value of the list nodes, the problem would be trivial. So, we are not allowed to modify the node values.
Table of Contents
Example
1 2 3 4
2 1 4 3
6 7 3
7 6 3
Approach
We can notice that we can swap the two nodes in a pair. The swap here means to manipulate the pointers so that the first node is connected to the remaining of the linked list and the second node now becomes head pointing to the first node.
The remaining list after this swap now becomes a sub-problem of what out initial problem was. So, we can call the same recursive function to the rest of the list. Here, we must keep track that the head of the list is now actually the second node in the list. This is a sufficient solution but consumes space because recursion creates stack frames in the memory.
The Optimal method can be easily thought as a similar approach implemented iteratively. For this purpose, we need to create a previous node that will store the tail of just previous pair we swapped. After swapping the nodes of the current pair, we connect the tail of the previous pair to head of this pair.
Algorithm(Recursive Approach)
- Simple base conditions are when do not even have two nodes to form a pair. In that case:
- The list can be NULL or can comprise one item.
- Return it as it.
- Now that we have a pair, use first and second to denote first and second items of our pair.
- Since the first node would now become the tail of this pair,
- call the recursive function starting from the next pair(node after second).
- The subproblem is solved by the function and append it to first node.
- Now, append the first node, which also has the rest of the list connected to it, to the second node.
- Since we want the second node to be swapped with first, second will become head now,
- Return second.
Algorithm(Optimal)
- Create a previous pointer pointing to some dummy node, maintain its prehead.
- Set next of the previous node as the current head of the list.
- This previous pointer can point to the next swapped pair.
- If the list is NULL or has just one element
- return the list
- Keep iterating till we reach a point where the list terminates or has just one node left:
- Store the address of next pair in a temp variable.
- Swap the two nodes in this pair: first node and the second node
- Connect the prevNode to the second node of this pair
- Update the prevNode as the first node(as it will become the tail now)
- Update head = temp so that we can jump to next pair
- The list still can be NULL or can have a single item left, so connect the prevNode to rest of the list.
- return dummy.next to get the required list.
Implementation
C++ Program to swap nodes in pairs leetcode solution
Recursive Approach
#include <bits/stdc++.h>
using namespace std;
struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};
void print(listNode* head)
{
while(head)
{
cout << head->value << " ";
head = head->next;
}
cout << '\n';
return;
}
listNode* swapNodesInPairs(listNode* head)
{
if(head == NULL || head->next == NULL)
return head;
listNode* first = head , *second = head->next;
first->next = swapNodesInPairs(head->next->next);
second->next = first;
return second;
}
int main()
{
listNode* head = new listNode(1);
head->next = new listNode(2);
head->next->next = new listNode(3);
print(swapNodesInPairs(head));
return 0;
}
Iterative Approach
#include <bits/stdc++.h>
using namespace std;
struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};
void print(listNode* head)
{
while(head)
{
cout << head->value << " ";
head = head->next;
}
cout << '\n';
return;
}
listNode* swapNodesInPairs(listNode* head)
{
if(head == NULL || head->next == NULL)
return head;
//initialise the prevNode
listNode *prevNode = new listNode(-1) , *prehead = prevNode;
prevNode->next = head;
listNode *first , *second , *temp;
//temporary variable to store first and second of every pair
while(head != NULL && head->next != NULL)
{
first = head;
second = head->next;
temp = second->next;
second->next = first;
prevNode->next = second;
//connecting previous node to the second of this pair
prevNode = first;
head = temp;
//reinitialising previous node and head for next pair
}
prevNode->next = head;
return prehead->next;
}
int main()
{
listNode* head = new listNode(1);
head->next = new listNode(2);
head->next->next = new listNode(3);
print(swapNodesInPairs(head));
return 0;
}
2 1 3
Java Program to swap nodes in pairs leetcode solutions
Recursive Approach
class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
}
class swap_nodes_in_pairs
{
public static void print(listNode head)
{
while(head != null)
{
System.out.print(head.value + " ");
head = head.next;
}
return;
}
public static listNode swapNodesInPairs(listNode head)
{
if(head == null || head.next == null)
return head;
listNode first = head , second = head.next;
first.next = swapNodesInPairs(head.next.next);
second.next = first;
return second;
}
public static void main(String args[])
{
listNode head = new listNode(1);
head.next = new listNode(2);
head.next.next = new listNode(3);
head.next.next.next = new listNode(4);
print(swapNodesInPairs(head));
}
}
Iterative Approach
class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
}
class swap_nodes_in_pairs
{
public static void print(listNode head)
{
while(head != null)
{
System.out.print(head.value + " ");
head = head.next;
}
return;
}
public static listNode swapNodesInPairs(listNode head)
{
if(head == null || head.next == null)
return head;
//initialise the prevNode
listNode prevNode = new listNode(-1) , prehead = prevNode;
prevNode.next = head;
listNode first , second , temp;
//temporary variable to store first and second of every pair
while(head != null && head.next != null)
{
first = head;
second = head.next;
temp = second.next;
second.next = first;
prevNode.next = second;
//connecting previous node to the second of this pair
prevNode = first;
head = temp;
//reinitialising previous node and head for next pair
}
prevNode.next = head;
return prehead.next;
}
public static void main(String args[])
{
listNode head = new listNode(1);
head.next = new listNode(2);
head.next.next = new listNode(3);
head.next.next.next = new listNode(4);
print(swapNodesInPairs(head));
}
}
2 1 4 3
Complexity Analysis
Time Complexity to swap nodes in pairs
Recursive Approach: O(N), as we only do a single pass on the list. Iterative Approach: O(N), again we do a single pass.
Space Complexity to swap nodes in pairs
Recursive Approach: O(N), as the recursion creates stack frames for every call in the memory. Iterative Approach: O(1), as constant space is used for some variables. This is where the iterative approach is better.