# \[83]\[简单]\[双指针]\[DFS] 删除排序链表中的重复元素

## 题目描述

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

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

```
输入: 1->1->2
输出: 1->2
```

示例 2:

```
输入: 1->1->2->3->3
输出: 1->2->3
```

## 解题思路

### 双指针

一个很明显的思路是双指针. 从head节点开始, 使用两个指针`left`和`right`, 如果两个指针对应节点的值相等, 则将`right`指针一直右移, 直到`right`指向的节点的值与`left`节点的值不同.

然后将`left`指向`right`即可. 再将`left`移至`right`, 重复上述过程, 直到`left`指向尾节点后的None.

由于head节点不会被删掉, 经过上述过程后, 直接返回原来的head节点即可.

### DFS

从递归的角度来看, 就是从head节点开始, 找到它的下一个节点, 然后指向它. 当前节点的下一个节点有两种情况:

* 后面的节点与其值不相等, 则下一个节点还是原来的节点
* 如果相等, 则可以一直跳过, 直到遇到不相等的节点, 就是下一个节点

对应的代码如下:

```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, second = node, node.next
            while second and first.val == second.val:
                second = second.next

            first.next = dfs(second)
            return first
        return dfs(head)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/shuang-zhi-zhen/83-shan-chu-pai-xu-lian-biao-zhong-de-zhong-fu-yuan-su.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.