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.

1.Swap in 4 group(Memory Limit Exceed)

public class longestSubstring {
    public ListNode swapPairs(ListNode head) {
        ListNode result=head.next;
        ListNode third = head.next.next;
        while (head.next.next != null) {
            head.next.next = head;
            if (third.next != null) {
                head.next = third.next;
                ListNode temp=third.next.next;
                third.next.next = third;
                head = third;
                third=temp;
            } else {
                head.next = third;
            }
        }
        return result;
    }
}

2 Recursion(simple but take a stcak of O(n), stack overflow)

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

3.Swap in 3 group, fake a dummy node(constant memory)