190. Swap Nodes in pairs in a Linked List by changing links

Objective: Given a linked list write an algorithm to swap nodes in pairs by changing links.

Earlier we have seen "Swap Every Kth node in a Linked List", where we have seen how to swap nodes by actually swapping the nodes In this article we will see how to swap nodes by changing the links.

Example:

Approach:

Iterative Method:

1. Take the 4 pointers ptrOne, ptrOne_prev, newhead and ptrTwo.
2. Make ptrOne = head and ptrTwo = head.next.
3. Store the reference of next node of ptrTwo, call it ptrTwoNext.
4. Make the ptrOne.next = ptrTwoNext. (we have just swap the ptrOne).
5. Make ptrOne_prev.next = ptrTwo; if ptrOne_prev is not null (swapped the ptrTwo).
6. Make the ptrTwo as newHead (this step will happen only once).
7. Move 2 nodes ahead for next pair wise swap.
8. See the code for more understanding.

Recursive Method:

1. This approach is easy compared to the iterative approach.
2. Change the links for the first two nodes.
3. Make the recursive call to the rest of the list.
4. See the code for more understanding.

Output:

Swapping Nodes using Iterative method
->2->1->4->3->6->5->7
Swapping again using Recursive method
->1->2->3->4->5->6->7

Related Problems:

- Reverse a linked list using stack Medium
- Locate the Farthest Left Node on the Bottom Level Medium
- In a Binary Tree, Create Linked Lists of all the nodes at each depth Hard
- Backtracking - Rat In A Maze Puzzle Hard
- Linked List cycle detection - Tortoise and Hare Algorithm Medium