> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/lian-biao/82-shan-chu-pai-xu-lian-biao-zhong-de-zhong-fu-yuan-su-ii.md).

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

## 题目描述

[82. 删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/)

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

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

示例 1：

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F59c613e1e8aeb56cf5edb2d89dc452a684545b24.jpg?generation=1616686614447684\&alt=media)

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

示例 2：

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F886e025aa786d41430cdd48d6e0673489ee2e661.jpg?generation=1616686614276235\&alt=media)

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

提示：

* 链表中节点数目在范围 \[0, 300] 内
* -100 <= Node.val <= 100
* 题目数据保证链表已经按升序排列

## 解题思路

### DFS

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

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

* 如果当前节点与后面的值相等, 当前节点要被删掉, 返回之后第一个值不同的节点为头节点的原子链, 对应的新的头节点
  * 不能直接返回之后第一个值不同的节点, 因为这个节点可能也有重复节点, 需要被删除, 因此要用**递归**的形式探索返回. 对应第二个例子的情况
* 如果当前节点的值与后面的节点不同, 说明当前节点肯定不会被删除, 探索后面子链的新的头节点, 然后将当前节点指向这个新节点, 最后返回当前节点

```python
# 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)
```

### 遍历

参考[【负雪明烛】递归+迭代，一篇题解吃透本题](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/fu-xue-ming-zhu-di-gui-die-dai-yi-pian-t-wy0h/). 使用双指针的方法.

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