LeetCode-Go 第 82 题：排序链表删除全部重复节点的五种 Go 实现与测试体系详解

LeetCode-Go 第 82 题：排序链表删除全部重复节点的五种 Go 实现与测试体系详解

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇以 LeetCode-Go 仓库中第 82 题（Remove Duplicates from Sorted List II，删除排序链表中的重复元素 II）的题解文档为主体，结合仓库内同一目录下的源码实现与单元测试，完整梳理题意边界、五种不同的 Go 解法（三指针迭代、递归、双循环、双指针加标志位、以及与第 83 题混淆的“保留一个副本”解法），并说明仓库中链表测试基建的搭建与运行方式。读完本文，你可以掌握虚拟头节点、尾递归递归跳过、删除标志位等链表的典型处理技巧，并理解该题“全部删除”与“去重保留一个”的本质区别。

题目与仓库目录结构

LeetCode-Go 将每道题放在leetcode/NNNN.题目名/目录下，第 82 题的目录为 leetcode/0082.Remove-Duplicates-from-Sorted-List-II，包含三个文件：

• README.md：题目、示例与中文题解思路；
• 82. Remove Duplicates from Sorted List II.go：五种解法实现（deleteDuplicates1～deleteDuplicates4与deleteDuplicates）；
• 82. Remove Duplicates from Sorted List II_test.go：Test_Problem82测试函数，覆盖空表、单节点、全重复、尾部成对重复等边界用例。

原题描述（完整继承自题解文档）

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:Input: 1->2->3->3->4->4->5，Output: 1->2->5

Example 2:Input: 1->1->1->2->3，Output: 2->3

题目大意：删除链表中重复的结点，只要出现过重复，这些节点要全部删除（一个都不留），最终链表中只保留从未重复过的数。这也是它与第 83 题（保留一个副本）的核心差异。

链表基建：structures 包与题内别名

仓库把通用数据结构抽到了独立的 structures 包中。链表节点定义在 structures/ListNode.go：

type ListNode struct { Val int Next *ListNode }

同文件还提供两个测试辅助函数：Ints2List（[]int转链表，空切片返回nil）与List2Ints（链表转[]int）。需要注意List2Ints内置了深度保护（见 structures/ListNode.go#L14-L34）：遍历超过 100 个节点即panic，用于防止误构造的环状链表导致死循环。

第 82 题的解法文件通过类型别名直接复用该定义（82. Remove Duplicates from Sorted List II.go#L8）：

type ListNode = structures.ListNode

而 go.mod 中的replace指令将github.com/halfrost/LeetCode-Go/structures指到仓库内./structures目录（go.mod#L5），因此无需额外安装任何依赖，go test即可在本地直接运行。

解法一 deleteDuplicates1：dummy 头 + 三指针迭代

这是测试用例实际调用的“基准”解法（82. Remove Duplicates from Sorted List II.go#L17-L61）：

func deleteDuplicates1(head *ListNode) *ListNode { if head == nil { return nil } if head.Next == nil { return head } newHead := &ListNode{Next: head, Val: -999999} cur := newHead last := newHead front := head for front.Next != nil { if front.Val == cur.Val { front = front.Next continue } else { if cur.Next != front { // 删除重复节点 last.Next = front if front.Next != nil && front.Next.Val != front.Val { last = front } cur = front front = front.Next } else { // 常规循环前 last = cur cur = cur.Next front = front.Next } } } if front.Val == cur.Val { last.Next = nil } else { if cur.Next != front { last.Next = front } } return newHead.Next }

实现要点：

• 虚拟头节点：用Val: -999999（小于 LeetCode 数据范围）的newHead挂到原head前，统一处理“头节点本身被删”的情况（如1->1->1->2->3输出2->3），最后返回newHead.Next。
• 三指针分工：front是快速前探指针，cur指向“待确认的唯一节点”，last是“已确认保留”的最后一个节点。当front与cur值相等时，说明cur所在值出现了重复，front继续前移直到遇到不同值；随后last.Next = front一次性跳过整段重复节点。
• last的惰性更新：只有当front.Next存在且值不同时才把last推到front，这样“尾部整段都是重复值”的情形（如1->1->1->1->1->1输出空表）可以在循环结束后用front.Val == cur.Val分支统一以last.Next = nil收尾。
• 时间复杂度 O(n)（每个节点最多被front扫过一次），空间 O(1)。

解法二 deleteDuplicates2：尾递归跳过重复段

82. Remove Duplicates from Sorted List II.go#L63-L75：

func deleteDuplicates2(head *ListNode) *ListNode { if head == nil { return nil } if head.Next != nil && head.Val == head.Next.Val { for head.Next != nil && head.Val == head.Next.Val { head = head.Next } return deleteDuplicates(head.Next) } head.Next = deleteDuplicates(head.Next) return head }

思路：若头节点值与下一节点相同，就把head一路推到这段重复值的末尾之后，再对整个剩余子表递归（“整段跳过”）；否则当前头节点保留，递归处理尾部后接回。这是五份实现中最简洁的一种，结构上属于尾递归，容易理解“值一旦重复则全段作废”的题意。局限在于递归深度为 O(n)，极端长链表下存在栈开销；从源码结构看，仓库并未对其做尾递归优化，长列表场景更推荐迭代写法。

解法三 deleteDuplicates3：虚拟头 + 双循环

82. Remove Duplicates from Sorted List II.go#L95-L116：

// 双循环简单解法 O(n*m) func deleteDuplicates3(head *ListNode) *ListNode { if head == nil { return head } nilNode := &ListNode{Val: 0, Next: head} head = nilNode lastVal := 0 for head.Next != nil && head.Next.Next != nil { if head.Next.Val == head.Next.Next.Val { lastVal = head.Next.Val for head.Next != nil && lastVal == head.Next.Val { head.Next = head.Next.Next } } else { head = head.Next } } return nilNode.Next }

外层循环每次只前进一步；一旦head.Next与head.Next.Next值相同，就把该值记入lastVal，内层循环持续把等值节点从链表中摘除（注意head指针本身不动，靠反复改写head.Next完成“原地剪链”）。注释标注 O(n·m)（m 为单个连续重复段的长度），是教学性质的朴素写法。以[1,2,2,2,2]为例：内层循环会把 4 个 2 全部摘除，外层终止后返回nilNode.Next，即[1]，与测试用例{[]int{1, 2, 2, 2, 2}, []int{1}}的期望一致。

解法四 deleteDuplicates4：双指针 + 删除标志位

82. Remove Duplicates from Sorted List II.go#L118-L156：

// 双指针+删除标志位，单循环解法 O(n) func deleteDuplicates4(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } nilNode := &ListNode{Val: 0, Next: head} // 上次遍历有删除操作的标志位 lastIsDel := false // 虚拟空结点 head = nilNode // 前后指针用于判断 pre, back := head.Next, head.Next.Next // 每次只删除前面的一个重复的元素，留一个用于下次遍历判重 // pre, back 指针的更新位置和值比较重要和巧妙 for head.Next != nil && head.Next.Next != nil { if pre.Val != back.Val && lastIsDel { head.Next = head.Next.Next pre, back = head.Next, head.Next.Next lastIsDel = false continue } if pre.Val == back.Val { head.Next = head.Next.Next pre, back = head.Next, head.Next.Next lastIsDel = true } else { head = head.Next pre, back = head.Next, head.Next.Next lastIsDel = false } } // 处理 [1,1] 这种删除还剩一个的情况 if lastIsDel && head.Next != nil { head.Next = nil } return nilNode.Next }

设计思路值得借鉴：不一次删完整段，而是**“每次发现相邻重复就只删前一个，留下后一个留给下一轮判重”**，用pre/back双指针预判相邻值，用lastIsDel记录上一轮发生过删除。若上一轮删过、且pre与back现在不等了，说明pre是重复段的“最后一个残留”，需要补删一次（第一个分支）；否则正常前进。循环结束后再补一句lastIsDel && head.Next != nil的收尾，专门处理[1,1]这种“整表只剩一段重复”的情形。

不过必须指出一个事实：按第 82 题“重复值全部删除”的题意，该实现对“尾部恰好构成重复对”的输入并不正确。以输入[0,1,2,2,3,4]为例手工推演：循环处理到末尾pre=2, back=4时触发补删分支，链表变为0->1->2->3->4并continue；下一轮pre=2, back=3不再相等且lastIsDel=false，指针正常前进，循环条件head.Next.Next != nil随后终止。最终得到[0,1,2,3,4]，保留了本应删除的 2。更关键的是，测试文件中对应用例的“期望值”本身就记录了这一偏差：

{ para82{[]int{0, 1, 2, 2, 3, 4}}, ans82{[]int{0, 1, 2, 2, 3, 4}}, },

（见 82. Remove Duplicates from Sorted List II_test.go#L71-L74。）该期望值既不符合题意（正确结果应为[0,1,3,4]），也与上面推演的[0,1,2,3,4]不同——之所以能“长期存在”，是因为测试函数只fmt.Printf打印、并不做断言（详见下文测试体系分析）。这里作为源码级事实予以披露：学习该实现时应以deleteDuplicates1或deleteDuplicates2的正确性为准。

解法五 deleteDuplicates：与第 83 题的易混点

文件末尾还有一个与题目同名的函数（82. Remove Duplicates from Sorted List II.go#L77-L93）：

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 }

这段代码只在遇到相邻重复时跳过“后一个”节点，cur不前进，因此同一值会保留一个副本——它实际上是第 83 题 Remove Duplicates from Sorted List 的解法（见 leetcode/0083.Remove-Duplicates-from-Sorted-List 目录）。对[1,1,1,1,1,1]它会输出[1]，而第 82 题要求输出空表。从源码结构看，它出现在本题目录中更像是一次“同族题对照”式的沉淀，读者在做题时务必区分：

测试体系：9 个边界用例与全解法覆盖

Test_Problem82 用question82{para82, ans82}组织输入输出对，共 9 组用例，系统性覆盖了链表去重题的典型边界：

1. [1,1,2,2,3,4,4,4] -> [3]：开头成对、中间成段、尾部成段混合；
2. [1,1,1,1,1,1] -> []：全表重复，验证“返回 nil/空表”；
3. [1,1,1,2,3] -> [2,3]：README 中的 Example 2，头部整段重复；
4. [1] -> [1]：单节点；
5. [] -> []：空表；
6. [1,2,2,2,2] -> [1]：尾部长重复段；
7. [1,1,2,3,3,4,5,5,6] -> [2,4,6]：多段交替；
8. [1,1,2,3,3,4,5,6] -> [2,4,5,6]：单重复对；
9. [0,1,2,2,3,4]：尾部重复对（上文已分析，其期望值记录了对deleteDuplicates4的偏差）。

测试循环里值得注意的是对五种实现全部调用的方式（82. Remove Duplicates from Sorted List II_test.go#L79-L86）：

for _, q := range qs { _, p := q.ans82, q.para82 fmt.Printf("【input】:%v 【output】:%v\n", p, structures.List2Ints(deleteDuplicates1(structures.Ints2List(p.one)))) deleteDuplicates2(structures.Ints2List(p.one)) deleteDuplicates3(structures.Ints2List(p.one)) deleteDuplicates4(structures.Ints2List(p.one)) deleteDuplicates(structures.Ints2List(p.one)) }

只打印deleteDuplicates1的结果并与para对照，其余四个函数被无断言调用——从源码结构看，这是为了在仓库“100% 覆盖率”目标（见 gotest.sh 中go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...）下让所有实现路径都进入coverage.txt统计，同时靠List2Ints的 100 节点深度限制兜底环状链表的 panic。使用时请注意：这组测试的断言强度依赖人工比对打印结果，属于“覆盖驱动”而非“断言驱动”，这也是上文deleteDuplicates4的偏差未被测试拦截的原因。

如何在本仓库中查看与运行

仓库为只读题解库，无需修改任何文件即可验证：

# 在仓库根目录，单独运行第 82 题的测试（可加 -v 查看输入输出对照打印） go test -v ./leetcode/0082.Remove-Duplicates-from-Sorted-List-II/ # 按仓库自带脚本生成全仓库覆盖率文件（与 CI 保持一致） ./gotest.sh

依赖方面，go.mod 要求 Go 1.19+，且通过replace指令将structures、template、ctl/util、ctl/models全部指向仓库内目录，Ints2List/List2Ints等测试辅助函数均来自 structures/ListNode.go，无需访问任何外部私有模块。

小结

第 82 题的题解文档只给出了两句式的思路提示，而仓库源码目录实际上沉淀了五种实现与 9 组边界用例的完整对照：deleteDuplicates1的三指针 + 虚拟头是覆盖最全的基准解法；deleteDuplicates2尾递归写法最贴近“重复段整段作废”的题意；deleteDuplicates3双循环、deleteDuplicates4双指针加标志位展示了不同的遍历组织思路（后者在尾部重复对场景存在正确性瑕疵，测试期望值亦如实记录了这一偏差）；与第 83 题同名的deleteDuplicates则是“保留一个副本”的对照实现。理解这些差异——尤其是“全部删除”与“去重留一”的语义边界、以及虚拟头节点对头部删除场景的统一处理——是本题对链表操作能力最重要的训练点。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go