题目
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
说明:
- 你的算法只能使用常数的额外空间。 - 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
坑点&思路
一开始理解错了，也没仔细看题目，两两交换，那不就是直接像冒泡一样，那么结果就是最前一个结点变到最后去。。。too yong too simple.（题目中文翻译的就是有点说不明白的感觉）
原来题目的意思是每两个相邻结点换一次，这个其实也很容易做到，就是把要交换的两个结点的next域变动一下，注意下交换顺序就可以，大概是下面这样的交换方式：
最开始是如下情况。
一旦n1.next 和 n1.next.next不是空，也就是说存在两个可以交换的结点，那么就交换并后移，like this：
1 | # do swap |
然后就成了这样：
然后就一直这样做下去就完事儿了。
不过要注意，我们思考的时候可以先给它标出n1、n2、n3、n4，写代码的时候一定要先判断它们都不为空，再进行变量赋值。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
41
42
43
44
45# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 链表为空或者只有一个结点
if head is None or head.next is None:
return head
# n1初始化在头指针之前
newList = ListNode(-1)
newList.next = head
n1 = newList
# 当存在两个相邻结点可以交换
while n1.next is not None and n1.next.next is not None:
n2 = n1.next
n3 = n2.next
n4 = n3.next
# do swap
n1.next = n3
n3.next = n2
n2.next = n4
# move pointer
n1 = n2
return newList.next
if __name__ == '__main__':
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
s = Solution()
list = s.swapPairs(head)
