# \[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)
```