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

怎样从“有序链表 1→1→2→3→3,删除重复使每个值只出现一次。”推导出 链表 · 去重，并证明每次状态变化都不会漏掉答案？

中心结论：扫描时若 cur.val==cur.next.val 则跳过 next,否则 cur 前进。

删除链表中重复的结点，以保障每个结点只出现一次。

在本站主例中，有序链表 1→1→2→3→3,删除重复使每个值只出现一次。

算法最终需要得到或观察：结果为 1→2→3。

复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“链表指针接力”，明确答案需要观察什么。
2. 2状态只维护 当前结点 cur、已去重前缀、待检查 next。
3. 3转移每一步按照 扫描时若 cur.val==cur.next.val 则跳过 next,否则 cur 前进。
4. 4收尾读取 结果为 1→2→3。，并复核边界与复杂度。

画清每根 next 指针改变前后的归属，再写代码。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：当前结点 cur、已去重前缀、待检查 next。

扫描时若 cur.val==cur.next.val 则跳过 next,否则 cur 前进。

执行过程中持续维护：当前结点 cur、已去重前缀、待检查 next。

正确性依赖以下不变量：cur 之前的结果段严格递增无重复。

面试时可以压缩为：有序链重复必相邻:while cur.next 且相等就 cur.next=cur.next.next;否则 cur 后移。

落到当前题，执行机制可以压缩为：扫描时若 cur.val==cur.next.val 则跳过 next,否则 cur 前进。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入有序链表 1→1→2→3→3,删除重复使每个值只出现一次。 因为：扫描时若 cur.val==cur.next.val 则跳过 next,否则 cur 前进。
2. 2取 a[0]=1较小者接入结果链,对应指针前进。 因为：保持结果链表有序。
3. 3取 a[1]=1较小者接入结果链,对应指针前进。 因为：保持结果链表有序。
4. 4取 b[0]=1较小者接入结果链,对应指针前进。 因为：保持结果链表有序。
5. 5取 a[3]=3较小者接入结果链,对应指针前进。 因为：保持结果链表有序。
6. 6取 b[1]=3较小者接入结果链,对应指针前进。 因为：保持结果链表有序。
7. 7取 a[5]=4较小者接入结果链,对应指针前进。 因为：保持结果链表有序。
8. 8收尾与复杂度结果为 1→2→3。 因为：时间 O(n) · 空间 O(1)。扫描时若 cur.val==cur.next.val 则跳过 next,否则 cur 前进。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func deleteDuplicates(head *ListNode) *ListNode {
	cur := head
	if head == nil {
		return nil
	}
	if head.Next == nil {
		return head
	}
	for cur.Next != nil {
		if cur.Next.Val == cur.Val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return head
}

func main() {
    // 1. 主例
    //    输入：mode="merge-two", values=[1,1,2,3,3,4]
    //    期望：结果为 1→2→3。
    //
    // 2. 失败 / 未命中
    //    检查：删除后要检查新的 cur.next,不能盲目 cur=cur.next。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC26 有序数组去重；LC82 删除重复 II
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意有序链表 1→1→2→3→3,删除重复使每个值只出现一次。
2. 2重复复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。
3. 3优化扫描时若 cur.val==cur.next.val 则跳过 next,否则 cur 前进。
4. 4证明cur 之前的结果段严格递增无重复。
5. 5复杂度时间 O(n)，空间 O(1)