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

题目描述

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

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

示例 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节点开始, 找到它的下一个节点, 然后指向它. 当前节点的下一个节点有两种情况:

• 后面的节点与其值不相等, 则下一个节点还是原来的节点

• 如果相等, 则可以一直跳过, 直到遇到不相等的节点, 就是下一个节点

对应的代码如下:

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