### 题目

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.

### 一次遍历 $O(n)$

#### 代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode sentinel = new ListNode(0), cursor = sentinel;
while (cursor.next != null && cursor.next.next != null) {
ListNode temp = cursor.next;
cursor.next = cursor.next.next;
temp.next = cursor.next.next;
cursor.next.next = temp;
cursor = cursor.next.next;
System.out.println(sentinel.next);
}
return sentinel.next;
}
}


### 还是一次遍历 $O(n)$， 优化指针

#### 代码

public class Solution {
ListNode sentinel = new ListNode(0);
ListNode cursor = sentinel, nextNode = cursor, afterNext = cursor;
while (cursor.next != null && cursor.next.next != null) {
nextNode = cursor.next;
afterNext = cursor.next.next;
nextNode.next = afterNext.next;
cursor.next = afterNext;
cursor.next.next = nextNode;
cursor = cursor.next.next;
}
return sentinel.next;
}
}


### 递归版 $O(n)$

#### 代码

public class Solution {
ListNode sentinel = new ListNode(0), cursor = sentinel;
ListNode nextNode = cursor.next, afterNext = nextNode.next;
swapPairsRecursive(cursor,nextNode,afterNext);
return sentinel.next;
}
public void swapPairsRecursive(ListNode cursor, ListNode nextNode, ListNode afterNext) {
nextNode.next = afterNext.next;
cursor.next = afterNext;
cursor.next.next = nextNode;
cursor = cursor.next.next;
if (cursor.next != null && cursor.next.next != null) {
swapPairsRecursive(cursor,cursor.next,cursor.next.next);
}
}
}


### 简化版递归$O(n)$

#### 代码

public class Solution {