Java有序链表去重代码测试[1,1,2]时生成无限链表问题求解

测试用例执行过程还原 #

针对测试用例[1,1,2]，逐行跟踪代码执行流程即可定位问题：

1. 初始状态：head指向第一个值为1的节点，节点关系为第一个1 → 第二个1 → 2 → null，哑节点l3、l4指向新建的哨兵节点。
2. 第一次进入while循环（此时head是第一个1，head.next是第二个1，满足head.next != null）：
   • 两个节点值相等，走if分支：head后移指向第二个1，l3.next赋值为head（即哨兵节点的next指向第二个1）
   • 执行l3 = l3.next后，l3和head都指向第二个1节点。
3. 第二次进入while循环（此时head是第二个1，head.next是2，满足head.next != null）：
   • 两个节点值不等，走else分支：
     • 第一步执行l3.next = head：此时l3和head都指向第二个1节点，相当于把第二个1节点的next指针指向自己，直接形成自环。
     • 第二步执行head = head.next，head后移指向2节点。
   • 执行l3 = l3.next：因为第二个1节点的next已经指向自己，所以l3始终停留在第二个1节点。
4. 第三次while判断：head是2节点，head.next为null，循环终止。

根因说明 #

最终返回的链表结构为哨兵节点 → 第二个1节点 ↺（第二个1节点的next指向自身），因此遍历链表时会无限读取值为1的同一个节点，形成你看到的无限链表现象。

代码修复方案 #

调整指针赋值逻辑避免同一节点自引用即可，参考修改后的代码：

public static ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (head != null) {
        // 跳过所有和当前head值重复的节点
        while (head.next != null && head.val == head.next.val) {
            head = head.next;
        }
        cur.next = head;
        cur = cur.next;
        head = head.next;
    }
    cur.next = null; // 收尾，避免末尾节点残留旧的next指针
    return dummy.next;
}

内容的提问来源于stack exchange，提问作者haloha