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!
Subscribe to get well-designed content on data structures and algorithms, machine learning, system design, oops, and mathematics. enjoy learning!
This game is played in a group, where players take turns to say the next number in a sequence, counting one at a time. If the number is divisible by 3, the player must say, “Fizz” instead of the number itself. If the number is divisible by 5, the player must say, “Buzz”. If the number is divisible by both three and five, the player has to say, “Fizz buzz”. Given a number n, write a program that outputs the string representation of numbers from 1 to n.
EnjoyAlgorithms
Recursion means solving the problem via the solution of the smaller sub-problem. This blog will answer some critical questions like - what is recursion? What are its advantages and disadvantages? How do you identify recursion problems? What is the difference between recursion and iteration? etc.
EnjoyAlgorithms
Given an array X[] with n elements, we need to write a program to find the maximum subarray sum among all subarrays. A subarray of array X[] of length n is a contiguous segment from X[i] through X[j] where 0<= i <= j <= n. Kadane algorithm idea is intuitive, using a single loop and few variables to solve the problem. We can use a similar idea to solve other coding problems.
EnjoyAlgorithms