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.

思路

这是一个单链表的题目，需要对连续两个节点进行操作。需要注意的是，不能改变链表的数值，只能修改结构。

将连接相邻节点的next指针重置即可得到结果

1
2
3
4
5
6
7
->1->2->3->4->5->6
  1 X 2 X 3->4->5->6
  1<-2 X 3->4->5->6
 ->2->1->4.....

将2指向1，1指向4，即完成一次转换。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if (head and head.next):
            cur1 = head
            cur2 = None
            cur3 = None
            # 用来指示是否是第一次操作，如果是，
            # 还需要更改头节点的指向，让头节点指向第二个节点
            firsttime = 1
            while (cur1 is not None):
                cur2 = cur1.next
                if (cur2):
                    cur3 = cur2.next
                    if (cur2.next and cur2.next.next):
                        cur1.next = cur2.next.next
                    else:
                        cur1.next = cur2.next
                    cur2.next = cur1
                else:
                    cur3 = None
                if (firsttime):
                    head = cur2
                cur1 = cur3
                firsttime = 0
        return head