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

约 4 分钟
文章信息 25 个分类 1 个标签
分类
LeetCode CodeTop 简单 已解决 需复习 50-100 腾讯 字节 阿里 华为 微软 美团 京东 小米 百度 网易 小红书 快手 滴滴 携程 虾皮 招行 商汤 旷视 猿辅导
标签
链表

题目描述

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

image-20260928194816956

image-20260928194816957

题意分析

给定一个按升序排列的链表，删除其中多余的重复节点，使每个不同的值只保留一个节点，并返回处理后的头节点。某个值出现多次时，仍然要保留它的一份，而不是删除这个值对应的整组节点。

链表已经有序，因此相同值一定连续出现。只要处理好每一段连续重复节点，就完成了整条链表的去重；空链表应直接返回空。

解法：单指针跳过连续重复节点

核心思路

[!blue]

用指针 cur 指向当前这组值准备保留的节点。它之前的部分已经完成去重，接下来只需要比较 cur 和它的后继：由于相同值连续出现，后继足以判断当前重复段是否已经结束。

若两者值相同，保留 cur，执行 cur.next = cur.next.next，让当前节点直接连向后继的后继。这是在链表连接中跳过一个多余节点，不需要复制节点或改变节点值。此时 cur 必须留在原地，因为新后继仍可能与它重复。

若两者值不同，当前值的重复段已经清理完成。由于链表升序，后面的节点不可能再次出现当前这个值，所以可以放心令 cur = cur.next，处理下一组。

每轮都会删除一个后继或把指针向后推进，未处理部分持续缩短。到达尾节点或空链表时结束。每组都保留第一个节点，所以原头节点不会被删除，也就不需要额外的哨兵节点；最终返回原来的 head。

解题步骤

  1. 令 cur = head，空链表会直接跳过循环。
  2. 当 cur 和 cur.next 都存在时，比较两者的值。
  3. 值相同：执行 cur.next = cur.next.next，继续检查当前 cur。
  4. 值不同：把 cur 前移一位。
  5. 扫描结束后返回 head，保留从头开始的整条结果链表。

代码实现

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;

        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                // 删除后当前代表节点不动，新后继仍可能是重复值。
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }

        return head;
    }
}

func deleteDuplicates(head *ListNode) *ListNode {
    cur := head
    for cur != nil && cur.Next != nil {
        if cur.Val == cur.Next.Val {
            // 删除后当前代表节点不动，新后继仍可能是重复值。
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return head
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 为节点数。每次比较都会删除当前后继或前进到该后继，每个原节点最多作为后继处理一次。
  • 空间复杂度：$O(1)$，只维护一个扫描指针，原地修改节点连接。

关键点总结

[!green]

  • 利用「有序 ⇒ 重复相邻」，把全局去重变成局部比较。
  • 删除重复节点后不能前进，否则会漏掉三个及以上的连续重复值。
  • 本题保留每组第一个节点，原头节点始终有效；删除整组重复值是另一种要求，不能混用处理逻辑。

易错点总结

[!yellow]

  • 删除重复后继后仍然推进 cur，会跳过对新后继的检查，连续多个重复节点可能没有清理干净。
  • 访问 cur.next 前必须先判断 cur 非空；访问后继的值和指针前，还要确保后继存在。
  • 返回扫描指针 cur 会丢掉前面已去重的节点，应返回一直保留的 head。
  • 相邻值不同时才能推进指针；不能发现重复后把当前代表节点也删除，否则会把该值的全部节点删掉。

相似题目

题目 难度 关联与区别
82. 删除排序链表中的重复元素 II 中等 同样识别有序重复段，原题删除该值的全部节点，本题保留一个代表。
26. 删除有序数组中的重复项 简单 同样利用相邻相等识别重复，数组用写指针覆盖，链表直接跳过节点。
19. 删除链表的倒数第 N 个结点 中等 用哨兵与前驱节点统一链表删改边界；本题每段重复值只保留一个，该题先用指针间隔定位倒数节点。
203. 移除链表元素 简单 用哨兵与前驱节点统一链表删改边界；本题每段重复值只保留一个，该题过滤所有目标值节点。
补充题 111. 提取有序链表中的重复值 中等 都利用有序链表中等值节点连续的性质逐段扫描；本题每段留一个，补充题只留下重复段。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/00102071
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！