本组囊括链表相关题目，难度不等。

24. Swap Nodes in Pairs

题目描述:中等

解法一：

考虑迭代解法，如果要两两交换相邻的节点，则这些节点肯定是相邻的奇偶节点，使用两个指针来遍历所有的奇偶节点。交换后将新节点的头指向第二个的头即可；
除了一个哨兵外，还需要定义一个指针current来更新链表,这个指针指向头节点；

 1 class Solution:
 2     def swapPairs(self, head: ListNode) -> ListNode:
 3         dummy = ListNode(0)
 4         dummy.next = head 
 5         current = dummy
 6         while head and head.next:
 7             # 定位到需要交换的节点
 8             firstNode = head
 9             secondNode = head.next
10 
11             # 开始交换并更新头节点
12             current.next = secondNode
13             firstNode.next = secondNode.next
14             secondNode.next = firstNode
15 
16             # 重新初始化head和curernt.next
17             current = firstNode
18             head = firstNode.next
19 
20         return dummy.next
21         # 时间复杂度： O(n)
22         # 空间复杂度： O(1)

 

83. Remove Duplicates from Sorted List

题目描述:简单

解法一：

这道题测试操作列表的结点指针的能力。由于输入的列表已排序，因此我们可以通过将结点的值与它之后的结点进行比较来确定它是否为重复结点。如果它是重复的，我们更改当前结点的 next 指针，以便它跳过下一个结点并直接指向下一个结点之后的结点。

 1 class Solution:
 2     def deleteDuplicates(self, head: ListNode) -> ListNode:
 3         # 迭代，遍历
 4         dummy = ListNode(0)
 5         dummy.next = head # 哑节点
 6         while head and head.next:
 7             if head.next.val == head.val:  # 如果全部都是重复的，那么最后第一个节点的next会指向None，即最后返回只会返回第一个指针。
 8                 head.next = head.next.next
 9             else:
10                 head = head.next
11         return dummy.next
12         # 时间复杂度： O(n)
13         # 空间复杂度： O(1)

 

 

82. Remove Duplicates from Sorted List II

题目描述:中等

解法一：

上一题是这道题的简版，只用删除重复的其他就行，这道题是需要删除所有重复的只保留没有重复出现的数字；
上一题做法是重复的话当前指针就指向下下个节点，这题的逻辑应该是如果重复的话当前节点的上一节点指针指向下下个节点，于是我们能想到的就是再多定义一个指针，用两个指针不断往前移动求解；
这里需要注意的是逻辑为两个指针指向下一个节点的值是否相等。

 1 class Solution:
 2     def deleteDuplicates(self, head: ListNode) -> ListNode:
 3         dummy = ListNode(0) # 哨兵节点
 4         dummy.next = head
 5         a = dummy
 6         b = head
 7         while b and b.next:
 8             if a.next.val != b.next.val:
 9                 a = a.next
10                 b = b.next
11             else:
12                 while b and b.next and a.next.val == b.next.val: # 若相等，则单独移动b指针，直到两个指针指向的下一个值不等。再移动b指针，让a指针指向b。
13                     b = b.next
14                 a.next = b.next
15                 b = b.next # 相对位置，b也移动
16         return dummy.next
17         # 时间复杂度： O(n)
18         # 空间复杂度： O(1)