Leetcode: Swap Nodes in Pairs

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.

Understand the problem:
The problem gives a linked list, swap every two adjacent nodes and return its head. For e.g. For 1->2->3->4, swap 1 and 2, 3 and 4, return 2->1->4->3. There are two requirements in the problem: you could only use constant space. You cannot modify the value in the list, just change the nodes. 

Let's take several examples to show the problem.
For a single node list, 1, return 1
For 1->2, return 2->1
For 1->2->3, return 2->1->3.
For 1->2->3->4->5, return 2->1->4->3->5

Solution:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */ public class Solution {     public ListNode swapPairs(ListNode head) {         if (head == null || head.next == null) return head;                   ListNode helper = new ListNode(0);         helper.next = head;                   ListNode pre = helper;         ListNode p = null;         ListNode q = null;         ListNode post = head;                   while (post != null) {             p = post;             q = post.next;             if (q == null) break;                           post = post.next.next;             pre.next = q;             q.next = p;             p.next = post;                           pre = p;         }                   return helper.next;     } }

A Neat Solution:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */ public class Solution {     public ListNode swapPairs(ListNode head) {         if (head == null || head.next == null) return head;                   ListNode helper = new ListNode(0);         helper.next = head;                   ListNode pre = helper;         ListNode cur = pre.next;                   while (cur != null && cur.next != null) {             pre.next = cur.next;             cur.next = cur.next.next;             pre.next.next = cur;                           pre = cur;             cur = pre.next;         }                   return helper.next;     } }

Update on 9/21/15:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) { val = x; }  * }  */ public class Solution {     public ListNode swapPairs(ListNode head) {         if (head == null || head.next == null) {             return head;         }                   ListNode dummyNode = new ListNode(0);         dummyNode.next = head;                   ListNode prev = dummyNode;         ListNode curr = head;                   int count = 0;                   while (curr != null) {             count++;             if (count % 2 == 1) {                 curr = curr.next;             } else {                 ListNode next = curr.next;                 curr.next = prev.next;                 prev.next.next = next;                 prev.next = curr;                                   prev = curr.next;                 curr = next;             }         }                   return dummyNode.next;     } }