Given you a Linked List like 1->2->3->4 ,would you be able to reform the list and into 2->1->4->3 without occupying more spaces?

So, the idea is to swap two adjacent nodes and once all the swappings are done, we return its head.

public ListNode swapPairs(ListNode head){

    if(head == null || head.next == null){
        return head;
    }
    
    ListNode dummy = new ListNode(0);
    
    dummy.next = head;
    
    head = dummy;
    
    while(head.next != null && head.next.next != null){
        
        ListNode n1 = head.next, n2 = head.next.next;
        // head->n1->n2 ... => head->n2->n1...
        
        head.next = n2;
        n1.next = n2.next;
        n2.next = n1;
        
        head = n1;
    
    }
    return dummy.next;

}

So, what's happening here?

Well, firstly we will do some simple checking make sure we take care of the edge cases, as you know, it's really no harm doing that in the beginning.

Then, we set a dummy node in front of the current node and had our head pointing at the dummy. Why are we doing that? Because when we do that, it will be easier for us to visualize the whole swapping process. How, you might ask?

head → n1 → n2 ...
head → n2 → n1 ...

So we use n1 to represent next node of head and n2 of next's next node. We know that the next node for head will be n2 and that n1's next node will be whatever the node n2 pointing to, which in this case is n2.next. Lastly, we need to make sure that n2 is pointing back to n1 again. Then we move our head to the next node.

Because the head node is never at the place where it needs to be swapped with another node, we don't need to worry about it being swapped whatsoever, we just need to make sure that the next two nodes are available to swap.

Remember the dummy node that we created earlier? We can simply return dummy.next as it is pointing at the initial head that we have set.

Hope this post helps!

Post was published on 28 Feb 2019, last updated on 2 Mar 2019.

Like the content? Support the author by paypal.me!