24. Swap Nodes in Pairs

1. 原始题目

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

2. 题目理解

给定一个链表，两两交换。

坑：空链表，奇数个结点的链表

3. 解题

思路：下图为初始状态。我们需要三个指针。head为新建的头结点。

第一次交换：

整理顺序后：

此时i j k顺序变了，不再是i j k。我们要循环，就得使得每次的顺序一致。所以：i = j; j = j.next; k = j.next

此时仍然可以交换，交换的是j和k的元素。交换完成后需要判断是否还要交换。不交换的条件是有两个：

情况1如上图，此时不在交换。

情况2如上图，此时不在交换。

代码实现:

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     def swapPairs(self, head: ListNode) -> ListNode:
 9         if not head or not head.next:
10             return head
11         
12         i = ListNode(0)      # 新建一个结点
13         i.next = head
14         new_head = i         # 用于记录
15         j = head
16         k = head.next
17         
18         while(k):
19             i.next = k        
20             j.next = k.next
21             k.next = j            # 以上3步常规操作
22             if (j):               # 情况1和情况2，退出循环
23                 i = j
24                 j = j.next
25             if (j):
26                 k = j.next
27             else:
28                 break
29             
30         return new_head.next    # 返回头结点

4. 验证

 1 # 新建链表1
 2 listnode1 = ListNode_handle(None)
 3 s1 = [1,2,3,4,5,6,8,999,666]
 4 for i in s1:
 5     listnode1.add(i)
 6 listnode1.print_node(listnode1.head)
 7 
 8 
 9 s = Solution()
10 head = s.swapPairs(listnode1.head)
11 listnode1.print_node(head)

1 2 3 4 5 6 8 999 666
2 1 4 3 6 5 999 8 666