跳到主要内容

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

题目描述​

Leetcode 地址

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

样例​

Input: 1->2->3->3->4->4->5
Output: 1->2->5

解题思路​

  • 伪节点：原因是头结点也可能会被删除

  • 双结点：用于节点删除操作

  • 通过 pre.next 来判断是否存在重复结点：

    • pre.next == cur ：证明 cur 没有移动，即没有重复值，pre 移动到 cur
    • pre.next != cur ：证明 cur 移动了，即存在重复值，pre 只删除重复值，不移动

代码​

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummpHead = ListNode(None) # 头结点也可能会被删除，故使用 伪节点
        dummpHead.next = head
        pre, cur = dummpHead, head # 双指针: 复制节点的删除
        while cur:
            # 检查是否存在重复节点
            while cur.next and cur.next.val == cur.val:
                cur = cur.next
            if pre.next == cur:  # 不存在重复节点，pre 前移
                pre = cur
            else:#  存在重复节点，pre 删除重复值
                pre.next = cur.next
            cur = cur.next # cur 前移
        return dummpHead.next