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 newHeadSolution 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:
- 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.
- 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.
- 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.
- 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 headSolution 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.
- Now, we swap the first pair of nodes, i.e., head and head->next.
- 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.
- We update the new head of the modified linked list: newHead = head->next.
- Finally, we update the next pointer of newHead to point to the head node: newHead->next = head.
- 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!
- 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 newHeadSolution 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
- 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!

