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.
---Jun 14 Review---
今天ustopia出了这题，写了一下，结果输入1,2,3,4这样返回了1,3。看了下答案，我漏写了一个preNode。因为我每次while过来，curS就开始指向nextS，那curEnd这个节点就没人指向了！所以需要一个pre来指向这个curEnd。那谁来指向curEnd，应该是被换到curEnd位置的curS。
至于为什么要fakeHead而不能用一个newNode保存head也很简单，head的地址没有改变没错，但是head已经不是首个node了。首个node是2不是1了。
另外，如果a，b，c都是对象，那a = b, b = c之后，a的地址会变成b的地址，b的地址会变成c的地址，但是a的地址不会随之再变成c的地址。这个跟List<Obj> 是不同的原理。List是一个整体的地址，里面的东西又是随意的其他的地址，里面的改变了不影响外面的。
---Mar 22 Review---
今天又看了一下这题，有几个注意点：
- 不能直接保存head，而要保存fakeHead，因为head会被
curStart = curStart.next;换到后面去。 - 巧妙地选取template。这题选了一个preNode，每一个piar里的第一个node(curStart)，下一个pair里的第一个node(nextStart)作为临时node。注意这个preNode是必不可少的，preNode=curS，curS = nextS;永远指向curS的前一个结点。例如下图中的步骤1。
- 画个图理解清楚就差不多了。
public ListNode swapPairs(ListNode head) {
if (head == null) return null;
//因为要return its head，所以把head保存下来
ListNode fakeHead = new ListNode(-1);
ListNode pre = fakeHead;
fakeHead.next = head;
ListNode curS = head;
while (curS != null && curS.next != null) {
// 之所以要定义这nextS是为了方便下次循环判断nextS是否是null pointer
ListNode nextS = curS.next.next;
pre.next = curS.next;
curS.next.next = curS;
curS.next = nextS;
pre = curS;
//这里亦可以写成：curS = nextS; 因为虽然nextS指向的是curS的引用，但是curS对象迄今为止并没有被改变过
curS = curS.next;
}
return fakeHead.next;
}
--第一次的版本--
这题思路简单，但是真正操作起来很绕。。
步骤是这样的：
(a,b)(c,d) 要变成(b,a)(d,c)
定义三个节点，pre.next = a，curStart = a，nextStart = c
- pre.next = curStart.next
- curStart.next = nextStart
- curStart.next.next = curStart
- pre = curStart , curStart = curStart.next
麻烦得一逼。要注意保存nextStart，因为curStart.next.next会被重定向到curStart。反正我不觉得面试时候我能一次写出来。。不过画个图也就差不多了。有个理解的技巧，对于curStart.next.next这种2连，可以把第一个curStart.next合起来想成结点，第二个next想成指针箭头。
public ListNode swapPairs(ListNode head) {
if (head == null) return null;
//因为要return its head，所以要把fakehead保存下来
ListNode fakeHead = new ListNode(0);
fakeHead.next = head;
ListNode pre = fakeHead;
ListNode curStart = head;
while (curStart != null && curStart.next != null) {
//nextStart要保存下来不然会丢
ListNode nextStart = curStart.next.next;
pre.next = curStart.next;
curStart.next.next = curStart;
curStart.next = nextStart;
pre = curStart;
curStart = curStart.next;
}
return fakeHead.next;
}
