Pairwise swap adjacent nodes of a linked list

Given a linked list, pairwise swap its adjacent nodes. The swapping of data is not allowed, only links should be changed.
For example,

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
Output: 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7 -> NULL
 
The idea is very simple. We traverse the linked list, consider two nodes at a time and swap their links. This looks simple enough but needs special attention while exchanging the links. This is demonstrated below in C –
Output: 

Before: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
After : 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7 -> NULL
 
The time complexity of above solution is O(n) where n is the number of nodes in the linked list.
 
We can also write recursive version of the above program. The idea remains the same but here we pass the next pair information and previous node through recursion.

Output:

Before: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
After : 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7 -> NULL


Learn More :