This post is completed by 1 user

  • 0
 Add to List
Medium

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:

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

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: