排除排序链表中的重复元素Ⅱ
题目要求
解题思路
题意：在一个有序链表中，如果一个节点的值出现不止一次，那么把这个节点删除掉
重点：有序链表，所以，一个节点的值出现不止一次，那么他们必相邻。
方法一：递归
链表和树的问题，一般都可以有递归和迭代两种写法。对于本题一定要记住是有序链表，值相同的节点会在一起。
1.1 递归函数定义
递归最基本的是要明白递归函数的定义！
递归函数直接使用题目给出的函数deleteDuplicates(head)，它的含义是删除以head作为开头的有序链表，值出现重复的节点。
1.2 递归终止条件
终止条件就是能想到的基本的、不用继续递归处理的case
- 如果
head为空，那么肯定没有值出现反复的节点，直接返回head； - 如果
head.next为空，那么说明链表中只有一个节点，也没有值出现重复的节点，也直接返回head
1.3 递归调用
什么时候需要调用递归呢？我们考虑两种情况：
- 如果
head.val != head.next.val，说明头节点的值不等于下一个节点的值，所以当前的head节点必须保留；但是head.next节点要不要保留呢？我们还不知道，需要head.next进行递归，即对head.next作为头节点的链表，去除值重复的节点。所以head.next = self.deleteDuplicates(head.next) - 如果
head.val == head.next.val，说明头节点的值等于下一个节点的值，所以当前的head，节点必须删除；但是head.next节点要不要删除呢？我们还不知道，需要一直向后遍历寻找与head.val不等的节点。与haed.val相等的这一段链表都要删除，因此返回deleteDuplicates(move)；
1.4 返回结果
题目让我们返回删除了值重复的节点后剩余的链表，结合上面两种递归调用的情况。
- 如果
head.val != head.next.val，头节点需要保留，因此返回的是head； - 如果
head.val == head.next.val，头节点需要删除，需要返回的是deleteDuplicates(move)。
迭代
方法二：一次遍历
这里说的一次遍历，是说一次遍历、一遍统计相邻节点的值是否相等，如果值相等就继续后移找到值不等的位置，然后删除值相等的这个区间
其实这个思路很简单，跟递归方法中的while语句跳过所有值相等的节点的思路是一样的：如果curr.val == cur.next.val说明两个相邻节点值相等，所以继续猴戏，一直找到cur.val !=cure.next.val，此时的cur.next就是值不等的节点；
代码中用到了一个常见的技巧：dummy节点，也叫做哑节点。
它在链表的迭代写法中非常常见，因为对于本题而言，我们可能会删除头节点head，为了维护一个不变的头节点，所以我们添加了dummy，让dummy.next = head，这样即使头节点被删除了，那么操作dummy.next指向新的链表头部，所以最终返回的也是dummy.next
方法三：利用计数，两次遍历
这个做法忽略了链表有序这个性质，使用了两次遍历，第一次遍历统计每个节点的值出现的次数，第二次遍历的时候，如果发现head.next的val出现次数不是1次，则需要删除head.next
代码
递归：
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
if head.val != head.next.val:
head.next = self.deleteDuplicates(head.next)
else:
move = head.next
while move and head.val == move.val:
move = move.next
return self.deleteDuplicates(move)
return head
迭代：
一次遍历：
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
dummy = ListNode(0)
dummy.next = head
pre = dummy
cur = head
while cur:
while cur.next and cur.val ==cur.next.val:
cur = cur.next
if pre.next ==cur:
pre = pre.next
else:
pre.next = cur.next
cur =cur.next
return dummy.next
两次遍历：
class Solution:
def deleteDuplicates(self, head):
dummy = ListNode(0)
dummy.next = head
val_list = []
while head:
val_list.append(head.val)
head = head.next
counter = collections.Counter(val_list)
head = dummy
while head and head.next:
if counter[head.next.val] != 1:
head.next = head.next.next
else:
head = head.next
return dummy.next
复杂度分析
递归：
时间复杂度：
O
(
N
)
O(N)
O(N)
空间复杂度：
O
(
N
)
O(N)
O(N)
迭代：
一次遍历
时间复杂度：
O
(
N
)
O(N)
O(N)
空间复杂度：
O
(
1
)
O(1)
O(1)文章来源：https://www.toymoban.com/news/detail-847334.html
两次遍历
时间复杂度：
O
(
N
)
O(N)
O(N)
空间复杂度：
O
(
N
)
O(N)
O(N)文章来源地址https://www.toymoban.com/news/detail-847334.html
到了这里，关于算法第四十一天-排除排序链表中的重复元素Ⅱ的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
