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.

 //non-recursive version
    public ListNode swapPairs(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head==null||head.next==null){
            return head;
        }
        ListNode runner = head;
        ListNode newHead = null;
        ListNode tail = null;
        while(runner!=null && runner.next!=null){
            ListNode runnernext = runner.next;
            ListNode runnernextnext = runnernext.next;
            if(tail!=null){
                tail.next = runnernext;                
            }else{
                newHead=runnernext;
            }
            runnernext.next = runner;
            runner.next = null;
            tail=runner;
            runner = runnernextnext;
        }
        if(runner!=null){
            tail.next = runner;
        }
        return newHead;
    }

//recursive version
    public ListNode swapPairs(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head==null||head.next==null){
            return head;
        }
        ListNode headnext =head.next;
        ListNode headnextnext=headnext.next;
        head.next = swapPairs(headnextnext);
        headnext.next=head;
        return headnext;
    }

Share