PROBLEM DESCRIPTION
Given a singly linked list. The task is to swap elements in the linked list pairwise. For example, if the input list is 1 2 3 4, the resulting list after swaps will be 2 1 4 3.
Note: You need to swap the nodes, not only the data. If only data is swapped then the driver code will print -1.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public Node pairwiseSwap(Node head) {
// Base case: if the list is empty or has only one node, no swap needed
if(head == null || head.next == null)
return head;
// save the head for next subproblem which we will solve using recursion
Node nextHead = head.next.next;
// break the link between current pair of nodes with rest of the list
head.next.next = null;
// Pointers to the current node (first of the pair) and the next node (second of the pair)
Node current = head;
Node nextNode = head.next;
// Swap: the second node points to the first node
nextNode.next = current;
// the current first node will need to point to the rest of the list after it has been "processed" using recursion
current.next = pairwiseSwap(nextHead);
// Return the new head of the swapped pair, i.e., the second node of the original pair
return nextNode;
}
}