当前:LC83 · 删除排序链表中的重复元素 · 首次出现于 Day 9 · 路径:顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC83 · Remove Duplicates from Sorted List · 链表

删除排序链表重复:同值就跳过后继

有序链表里相同值挤成一段。cur 只看后继:值相同就让 Next 越过它,自己不动;值不同才前进。连着三个 1,必须停在第一个 1 上连跳两次。

cur 从 head 出发。cur 与后继都在时:值相同则 cur.Next = cur.Next.Next,cur 不动;值不同则 cur = cur.Next。也可以看成慢指针停在保留节点、快指针探过相同段。时间 O(n),空间 O(1)。

时间 O(n)空间 O(1)结论先行 · 全文约 6 节
导读

给定一个升序链表的头,删掉所有重复值,使每个数只出现一次,返回新链表的头。节点相对顺序不变。

主例 1→1→2→3→3。两个 1 相邻,两个 3 相邻。删完是 1→2→3。题目保留第一次出现的那个节点,不是整段都扔掉——那是 LC82。

无序链表得先记住见过的值。有序把「找重复」收成「看隔壁」。本文要回答:为什么跳过重复时不能把 cur 一起挪走。

相邻同值就跳,cur 停在第一次出现的地方

链表已经升序,同一个值只可能连成一段,不会在后面突然再冒出来。于是扫描时只需要比较 cur 和 cur.Next。值不同,这段结束,cur 前进。值相同,后继是多余的那一个,把它从链上摘掉:cur.Next = cur.Next.Next。

缺的是「摘掉之后 cur 还停不停」。若摘完立刻 cur = cur.Next,主例还看不出来——两个 1 只跳一次。把开头改成 1→1→1→2:第一次跳过第二个 1,若 cur 跟着走到第三个 1,就再也看不到「当前保留的 1 和下一个 1 相同」,三个 1 会留下两个。所以同值时只改 Next,cur 仍停在第一次出现的节点上,新的后继若还相同,下一轮继续跳。

这和快慢指针是同一件事。慢指针停在要保留的节点,快指针往前探;快指针值还等于慢指针,就让慢指针的 Next 越过快指针。代码把快指针省成 cur.Next,少一个变量,判断一样。

用手走主例。cur 停在第一个 1,后继也是 1,跳过,链变成 1→2→3→3。演示第一帧。cur 不动,再看后继,现在是 2,值不同,cur 走到 2。演示第二、三帧。2 的后继是 3,不同,cur 走到第一个 3。后继还是 3,跳过,链变成 1→2→3。后继空,结束。演示最后一帧。

空链表、单节点、完全无重复,循环里每一次都是异值前进,头指针不用换。整段都是同一个值,cur 停在头上连跳到只剩自己。头节点若重复,留下的仍是原来的 head,所以函数直接返回 head,不必另找新头。

同值时为什么不走 cur新的后继可能仍等于 cur。cur 一走,这段里后面的重复就没人再跟「第一次出现的值」比。连着三个相同值时会漏删。
cur 与后继比较:相同则跳过
1cur
1
2
3
3
cur=1,Next=1 相同 → 跳过

Go:单指针跳过

solution.goGo
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
}

1cur 从 head 出发。空链表时循环不进,直接返回。

2后继也在才有得比。少了 Next 判空会解引用空指针。

3同值只改 Next,cur 不动,才能连删一段。

4异值才前进。头节点始终是第一次出现的最小值,直接返回 head。

总结

有序则重复相邻:同值跳过后继且 cur 不动,异值前进。主例留下 1→2→3。

  • 无序才需要集合。有序只比隔壁。
  • 同值时 cur 停在第一次出现的节点。1→1→1 必须连跳两次。
  • 本题留第一次;LC82 要把整段相同值都删掉,需要前驱。
同族题目
LC82删除排序链表中的重复元素 IILC26删除有序数组中的重复项LC206反转链表