如何正确删除有序链表中的重复元素（LeetCode #83）-java教程-PHP中文网

如何正确删除有序链表中的重复元素（LeetCode #83）

本文详解 LeetCode 第 83 题“删除排序链表中的重复元素”的常见逻辑错误与正确解法，重点剖析 head != head.next 的误用、空指针风险、结果指针更新时机等关键陷阱，并提供两种稳健实现方案。

本文详解 leetcode 第 83 题“删除排序链表中的重复元素”的常见逻辑错误与正确解法，重点剖析 `head != head.next` 的误用、空指针风险、结果指针更新时机等关键陷阱，并提供两种稳健实现方案。

在解决 LeetCode #83 —— “删除排序链表中的重复元素”时，一个典型误区是误将引用比较当作值比较使用。原始代码中 if (head != head.next) 这一条件始终为 true：因为 head 和 head.next 是两个不同的对象引用（除非链表成环，但本题输入为普通单链表），该判断完全无法检测数值是否重复，纯属逻辑失效。

更严重的是，原代码未做 head.next == null 的前置校验，直接访问 head.next.val 会导致 NullPointerException；同时，result = result.next 被置于循环末尾，导致无论是否跳过重复节点，结果链表都会无条件追加一个新节点——这正是输出 [1,1,2,3,3] 而非 [1,2,3] 的根本原因。

✅ 正确思路应分为两类实现方式：

方式一：双指针原地修改（推荐，空间 O(1)）

利用链表已排序特性，仅需一次遍历，通过调整 next 指针跳过连续重复节点：

快搜

一款AI工具，主要用于快搜旗下人工智能搜索引擎服务，适合需要提升相关任务效率的用户。

下载

public ListNode deleteDuplicates(ListNode head) {
    ListNode temp = head;
    while (temp != null && temp.next != null) {
        if (temp.val == temp.next.val) {
            temp.next = temp.next.next; // 跳过重复节点
        } else {
            temp = temp.next; // 仅当值不同时才移动指针
        }
    }
    return head;
}

⚠️ 注意：此方法不创建新节点，直接修改原链表结构，时间复杂度 O(n)，空间复杂度 O(1)，且天然规避空指针问题（因 while 条件已确保 temp.next != null 才进入循环体）。

方式二：虚拟头节点 + 显式构建（清晰易懂）

若倾向新建结果链表，必须严格控制 result 指针的移动时机：仅当确认当前节点为非重复首节点时，才将其接入结果链并推进 result：

public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(-1);
    ListNode result = dummy;

    while (head != null) {
        // 关键判断：当前节点是末尾，或与下一节点值不同 → 保留
        if (head.next == null || head.val != head.next.val) {
            result.next = head;
            result = result.next; // ✅ 仅在此处推进 result
        }
        head = head.next; // ✅ head 始终推进（无论是否保留）
    }

    return dummy.next;
}