Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Swap Nodes in pairs in a Linked List by changing links

Objec­tive: Given a linked list write an algo­rithm to swap nodes in pairs by chang­ing links .

Ear­lier we have seen “Swap Every Kth node in a Linked List”, where we have seen how to swap nodes by actu­ally swap­ping the nodes but In this arti­cle we will see how to swap nodes by chang­ing the links.

Exam­ple:

Swap Nodes in pairs in a Linked List by changing links

Swap Nodes in pairs in a Linked List by chang­ing links

Approach:

Iter­a­tive Method:

  1. Take the 4 point­ers ptrOne, ptrOne_prev, new­head and ptrTwo.
  2. Make ptrOne = head and ptrTwo = head.next.
  3. Store the ref­er­ence of next node of ptrTwo, call it ptrTwoNext.
  4. Make the ptrOne.next = ptrT­woNext. (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 new­Head (this step will hap­pen only once).
  7. Move 2 nodes ahead for next pair wise swap.
  8. See the code for more understanding.

Recur­sive Method:

  1. This approach is easy com­pare to iter­a­tive approach.
  2. Change the links for first two nodes.
  3. Make the recur­sive call to rest of the list.
  4. See the code for more understanding.

Com­plete Code:

Out­put:

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

You may also like...