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/Java –

C

Download   Run Code

Output:

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

Java

Download   Run Code

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.

C

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (5 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of