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.
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
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.
Before starting the loop:
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).
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
Now, we swap the first pair of nodes i.e. head and head->next.
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.
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
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
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)
We are using constant extra space, so space complexity = O(1)
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.
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)
Enjoy learning, Enjoy coding, Enjoy algorithms!