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:
Approach:
Iterative Method:
- Take the 4 pointers ptrOne, ptrOne_prev, newhead and ptrTwo.
- Make ptrOne = head and ptrTwo = head.next.
- Store the reference of next node of ptrTwo, call it ptrTwoNext.
- Make the ptrOne.next = ptrTwoNext. (we have just swap the ptrOne).
- Make ptrOne_prev.next = ptrTwo; if ptrOne_prev is not null (swapped the ptrTwo).
- Make the ptrTwo as newHead (this step will happen only once).
- Move 2 nodes ahead for next pair wise swap.
- See the code for more understanding.
Recursive Method:
- This approach is easy compare to iterative approach.
- Change the links for first two nodes.
- Make the recursive call to rest of the list.
- See the code for more understanding.
Complete Code:
| public class PairwiseSwapNodesByChangingLinks { | |
| public static Node swapNodeIterative(Node head){ | |
| Node ptrOne_prev = null; | |
| Node baseHead = null; | |
| while(head!=null && head.next!=null ){ | |
| //Take 2 pointers, one on head | |
| Node ptrOne = head; | |
| //another on head.next | |
| Node ptrTwo = head.next; | |
| //store the reference of next node of pointer 2. | |
| Node ptrTwoNext = ptrTwo.next; | |
| // make the pointer 1 points to pointer2 next. | |
| ptrOne.next = ptrTwoNext; | |
| if(ptrOne_prev!=null){ | |
| // link the next pair swap to the previous one | |
| ptrOne_prev.next = ptrTwo; | |
| } | |
| else{ | |
| // pointer 2 will become the new head after the first swap. | |
| baseHead = ptrTwo; | |
| } | |
| //reverse the next link of pointer 1. | |
| ptrTwo.next = head; | |
| //move 2 modes forward for next pairwise swap. | |
| ptrOne_prev = ptrOne; | |
| head = ptrTwoNext; | |
| } | |
| return baseHead; | |
| } | |
| public static Node swapNodeRecursive(Node head){ | |
| if(head==null || head.next==null){ | |
| return head; | |
| } | |
| //change the link for first 2 nodes and | |
| //make a recursive call to rest of the list. | |
| Node ptrOne = head; | |
| Node ptrTwo = head.next; | |
| Node ptrTwoNext = ptrTwo.next; | |
| ptrTwo.next = head; | |
| Node newhead = ptrTwo; | |
| ptrOne.next = swapNodeRecursive(ptrTwoNext); | |
| return newhead; | |
| } | |
| public static void display(Node head){ | |
| //System.out.println(""); | |
| Node currNode = head; | |
| while(currNode!=null){ | |
| System.out.print("->" + currNode.data); | |
| currNode=currNode.next; | |
| } | |
| } | |
| public static void main (String[] args) throws java.lang.Exception | |
| { | |
| Node head = new Node(1); | |
| head.next = new Node(2); | |
| head.next.next = new Node(3); | |
| head.next.next.next = new Node(4); | |
| head.next.next.next.next = new Node(5); | |
| head.next.next.next.next.next = new Node(6); | |
| head.next.next.next.next.next.next = new Node(7); | |
| Node x = swapNodeIterative(head); | |
| System.out.println("\n Swapping Nodes using Iterative method"); | |
| display(x); | |
| System.out.println("\n Swapping again using Recursive method"); | |
| Node n = swapNodeRecursive(x); | |
| display(n); | |
| } | |
| } | |
| class Node{ | |
| public int data; | |
| public Node next; | |
| public Node(int data){ | |
| this.data = data; | |
| this.next = null; | |
| } | |
| } |
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
The recursive solution is very elegant.
http://ideone.com/gCcARV