Swap Nodes in Pairs

Description

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.

Method

non- recursive method:

firstly use dummy node to mark the head; Secondly use three pointers switch a pair of node

recursive method: make switch as a unit operation and then call it in inner method

Time and Space Complexity

O(n)

Code

for 1:

public class Solution {

public ListNode swapPairs(ListNode head) {
       if (head == null || head.next == null){
           return head;    
       }
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       ListNode pre = dummy;
       ListNode first = head;
       ListNode second = head.next;
       while (second != null){
           pre.next = second;
           pre = second.next;
           second.next = first;
           first.next = pre;
           if (pre == null){
               break;
           }
           second = pre.next;
           pre = first;
           first = first.next;
       }
       return dummy.next;
}

}

for 2:

public class Solution {

public ListNode swapPairs(ListNode head) {
    ListNode x = null;
    if (head == null || head.next == null){
        return head;
    }
    x = head.next;
    head.next = x.next;
    x.next = head;
    head.next = swapPairs(head.next);
    return x;
}

}