24. Swap Nodes in Pairs Leetcode Java

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Solution:

Transverse two nodes each time, maintain a pre pointer, do the swap each time when there is still two or more nodes after pre node. The swap is straightforward, for example to swap 1->2,->3 and assume there is a pre node before the node 1. cur=1, pre.next=1.next(:2), 1.next=1.next.next(:3), pre.next.next(:2.next)=cur(:1), pre=cur(:1) after doing this: oldpre->2->1->3, and the current pre node is becoming 1 node.

A little trick here is to build a dummypre node and put its next as the original head, by doing this, we can avoid a lot of trouble for taking care of the head corner case. And also it is very helpful for final result return.

 public ListNode swapPairs(ListNode head) {  
    if(head==null || head.next==null) return head;  
    ListNode predummy=new ListNode(0);  
    predummy.next=head;  
    ListNode pre=predummy;  
    while(pre.next!=null && pre.next.next!=null){  
      ListNode cur=pre.next;  
      pre.next=cur.next;  
      cur.next=cur.next.next;  
      pre.next.next=cur;  
      pre=cur;  
    }  
    return predummy.next;  
   }