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 but 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 compare to iterative approach.
  2. Change the links for first two nodes.
  3. Make the recursive call to rest of the list.
  4. See the code for more understanding.

Complete Code:



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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: