[82][中等][DFS] 删除排序链表中的重复元素 II

题目描述

82. 删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内

• -100 <= Node.val <= 100

• 题目数据保证链表已经按升序排列

解题思路

DFS

作为[83][简单][双指针][DFS] 删除排序链表中的重复元素的演变, 我们可以接续采用DFS寻找下一个节点的思路. DFS函数返回的是以当前节点为头节点的原子链, 新的头节点是哪个节点.

由于要删掉相同元素的头节点, 因此:

• 如果当前节点与后面的值相等, 当前节点要被删掉, 返回之后第一个值不同的节点为头节点的原子链, 对应的新的头节点

  • 不能直接返回之后第一个值不同的节点, 因为这个节点可能也有重复节点, 需要被删除, 因此要用递归的形式探索返回. 对应第二个例子的情况

• 如果当前节点的值与后面的节点不同, 说明当前节点肯定不会被删除, 探索后面子链的新的头节点, 然后将当前节点指向这个新节点, 最后返回当前节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        def dfs(node):
            if node is None or node.next is None:
                return node

            first, current = node, node.next
            while current and first.val == current.val:
                current = current.next

            if first.next is not current:
                return dfs(current)
            else:
                first.next = dfs(current)
                return first

        return dfs(head)

遍历

参考【负雪明烛】递归+迭代，一篇题解吃透本题. 使用双指针的方法.

需要特别注意的是使用了dummy节点(哑节点) 这一种 哨兵 技巧, 大大简化了头节点被删除这种特殊情况的处理方法. 在头节点之前增加一个dummy节点, 头节点也就变成了链中的节点, 不再特殊. 返回的时候, 直接返回dummy.next即可.