企业官网建设流程全解析

先说个我刷题时的真实感受：很多人在LeetCode上遇到“83. 删除排序链表中的重复元素”这道题，第一反应是“这不就是Easy题嘛”，然后写个HashSet或者新建一个链表，顺手就交了。等面试的时候被面试官追问一句“你能不用额外空间吗”，或者让你现场把边界条件画一遍，不少人就卡住了。这道题确实不难，但它是检验链表基本功的一道好题——你是在机械地记忆代码，还是真的理解了单链表的结构、指针语义和有序性带来的便利，一测便知。下面我用实际做题的思路，把这题从头到尾拆开讲透，并把这套思路延伸到高频变体题和真实面试场景里。

1. 为什么“有序”这两个字，是这题的题眼

先回到题目本身：给定一个已排序的链表，删除所有重复的元素，让每个元素只出现一次。比如输入1 -> 1 -> 2，输出1 -> 2；输入1 -> 1 -> 2 -> 3 -> 3，输出1 -> 2 -> 3。

如果只盯着“删除重复元素”这六个字，很容易往“记录出现过的值”这个方向想。很多人的第一版解法就是弄一个哈希集合，遍历链表，如果当前值没出现过就保留，出现过就跳过。这样做当然能通过，时间复杂度O(n)，空间复杂度却是O(n)。

但这道题里有一个被低估的前提条件：链表是排序好的。这意味着什么？意味着所有重复的值在物理位置上一定是紧挨着的。既然重复项一定是连续的一段，我们根本不需要记住之前见过哪些值，只需要比较“当前节点”和“下一个节点”是否相等就够了。因为如果当前节点和下一个节点不相等，那下一个节点和后面某些节点相等的可能性完全不影响当前节点——当前节点已经可以直接保留。

这个“相邻比较”的思路，让空间复杂度降到了O(1)。这也是面试官期待的答案：利用数据有序性，把哈希表的额外空间省掉。说实话，算法题里很多优化都来自同一个套路——“别处理所有情况，去处理你真正需要处理的情况”，而有序性就是那个能让你“偷懒”的合法理由。

2. 单链表里“删除”到底是什么：指针操作的本质

在写代码前，我建议先把链表的物理结构在脑子里过一遍。链表不是数组，它的节点在内存里是分散的，每个节点只知道自己后面是谁。定义一个节点长这样：

public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }

一个链表节点就两个信息：当前的数值val，以及指向下一个节点的引用next。

在链表上做“删除”，本质上不是把节点从内存里抹掉——在Java里我们也没有这个能力，那是GC的事。删除的核心操作是改写引用：让前一个节点的next指向被删节点的下一个节点。一旦没有任何引用指向被删节点，它就会被垃圾回收机制自动清理。

比如链表A -> B -> C，要删除B，只需要让A.next = C。这里有个初学者很容易绕进去的误区：删除节点时，我们根本不关心被删除节点的next指向哪里，也不需要显式释放内存。你只需要保证一个前提：删除操作发生前，必须持有被删节点的前一个节点。

为什么呢？因为单链表只能从前往后走。我在B这个位置，我能拿到B.next，但我拿不到B.prev——根本不知道是谁指向B。所以删除时必须用一个指针停留在B前面的A上，通过修改A.next来“跳过”B。这就是这题迭代解法里，cur指针为什么必须停留在重复段的前一个节点上的根本原因。

很多同学看完答案能默写，但把“让指针停在正确的位置”这个逻辑吃透的人不多。一旦你真正理解了它，后面碰到任意链表删除题，你都不会再怕。

3. 迭代解法：最容易写错的是“什么时候该移动cur”

直接给代码，然后再拆解里面的判断逻辑：

class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode cur = head; while (cur != null && cur.next != null) { if (cur.val == cur.next.val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; } }

代码只有十行左右，但你要注意一个细节：当遇到重复时，我让cur.next指向cur.next.next，但是cur本身没有移动。这是这道题我最想强调的地方。

假设链表是1 -> 1 -> 1 -> 2。如果用cur = cur.next来处理相等的情况：

• 第一轮，cur在第一个1，cur.next也是1，相等，处理完之后cur跑到第二个1；
• 第二轮，cur在第二个1，cur.next还是1，相等，处理完之后cur跑到第三个1；
• 第三轮，cur在第三个1，cur.next是2，不相等，继续移动。

看起来好像也能跑？不对，你再仔细看：第一轮处理完之后，链表结构会变，但如果你同时把cur往前移动，就会滑过新暴露出来的重复节点。正确做法是：当发现当前节点和下一个节点值相等时，只修改cur.next的指向，把下一个节点“跨过去”，然后停在原地继续比较当前节点和新的下一个节点。因为旧的cur.next被替换了，新的cur.next仍然可能是相同值。

处理完重复后，cur指向的节点的下一个节点才是不同的值，此时cur = cur.next才能安全地前进。

再看一下边界情况：

• 空链表：head = null，while条件直接不满足，返回null，没问题。
• 只有一个节点：cur.next == null，循环退出，返回原节点，没问题。
• 结尾连续重复：比如1 -> 2 -> 2 -> 2。cur在2时发现和cur.next相等，就不断执行cur.next = cur.next.next，直到cur.next为null或值不同。循环结束时cur仍然指向第一个2，但后续重复项已经被跨过了。

用Python写逻辑完全一样：

class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: cur = head while cur and cur.next: if cur.val == cur.next.val: cur.next = cur.next.next else: cur = cur.next return head

提示：这段代码里有一个隐含假设——head本身的值不会被改变，所以最后直接返回head。如果这道题要求“只要重复就一个不留”，那个场景下头节点可能被删，就必须用dummy node了。这点我在第5章会细说。

复杂度方面，每个节点最多被访问一次，时间复杂度O(n)，没有使用哈希表，空间复杂度O(1)。这也是解法中最优的时空表现。

4. 递归解法：用“递”的视角看这个问题的分层结构

除了迭代，还可以用递归写。递归解法的存在意义不完全在于效率，而是帮助我们从另一个角度理解链表的结构——链表本质上是一种递归定义的数据结构：一个节点后面跟着另一个链表。

递归的思路是这样的：我处理当前节点时，先别管后面的重复情况，我只确保两个东西：

1. 如果当前节点和下一个节点值相同，我就“跳过”当前节点，直接返回“对下一个节点递归处理”的结果。
2. 如果当前节点和下一个节点值不同，我就保留当前节点，当前节点的next指向“对后面链表递归处理”的结果。

代码长这样：

class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } head.next = deleteDuplicates(head.next); if (head.val == head.next.val) { return head.next; } else { return head; } } }

走一遍1 -> 1 -> 2：

• 最外层递归，head在第一个1，先递归处理后面的1 -> 2；
• 第二层递归，head在第二个1，先递归处理后面的2；
• 第三层递归，head在2，2.next为null，返回2；
• 回到第二层：head.next等于第三层的返回值2，比较第二个1.val和2.val，不相等，返回第二个1，所以第二层返回的是1 -> 2；
• 回到第一层：head.next等于第二层的返回值1 -> 2，比较第一个1.val和1.val，相等，返回head.next，也就是1 -> 2。

整个过程中，每一层只负责“当前节点和子链表头节点”的关系，重复节点就像一个一个被“剥掉”的洋葱皮。递归的终止条件是当前节点为null或只有一个节点——这是递归题的通用底线。

递归解法的空间复杂度是O(n)，因为递归调用栈要存每一层的信息。在链表非常长（几万个节点）时，理论上可能触发栈溢出，所以生产级代码里迭代解法更稳妥。但递归版本在面试里可以作为补充答案展示思路，面试官很吃这一套——能讲清楚递归调用栈的进出过程，说明你真的理解了链表的递归本质。

5. 一个极容易被忽略的问题：为什么这题不需要dummy node

刷题多的人对dummy node（虚拟头节点）一定不陌生，它长这样：

ListNode dummy = new ListNode(-1); dummy.next = head;

`,在需要删除头节点的题目里，dummy是必杀技。但这道题很多答案都没有用dummy，原因是：这题的头节点永远不会被删除。

为什么？因为题目要求的是“保留一个”。如果一个值出现了多次，我们保留的是这组重复值中的第一个，而头节点恰好就是第一组重复值的第一个。无论后面的节点怎么删，头节点始终被保留。所以最后可以理直气壮地return head。

但如果你做的是变体题LeetCode 82“删除排序链表中的重复元素II”，要求“只要元素出现重复，就全部删除，一个不留”，情况就不一样了：如果整个链表是1 -> 1 -> 2 -> 3，头节点1是重复的，必须被删掉。这时候head本身可能被删除，你就必须引入dummy node来占住位置，最后返回dummy.next。

这个对比本身就是一道很好的面试追问。面试官常常会用这种“同场景不同要求”的方式来考察你：你不是背了两道题吗？那请你讲讲这两道题用不用dummy的本质区别是什么。区别就一句话：当且仅当链表的头节点有可能被删除时，才需要dummy node。这是一个在链表题里放之四海而皆准的判断标准。

6. 从这题延伸开去：变体题和面试追问的应对思路

这道题在面试中经常自带“加餐题目”，刷题不用只盯着83题本身，最好把下面这些变体一起搞清楚。

6.1 LeetCode 82：重复元素一个不留

核心代码逻辑和83题不同，不能简单地“保留一个”，而是要把一整段重复值全部跨过去：

class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null) return head; ListNode dummy = new ListNode(-1, head); ListNode cur = dummy; while (cur.next != null && cur.next.next != null) { if (cur.next.val == cur.next.next.val) { int val = cur.next.val; while (cur.next != null && cur.next.val == val) { cur.next = cur.next.next; } } else { cur = cur.next; } } return dummy.next; } }

这个解法里有两个关键点：一是用dummy兜底，因为头节点可能被当成重复元素删掉；二是用while而不是if来处理整段重复。当发现cur.next.val == cur.next.next.val时，先把重复值记下来，然后不停地把cur.next往后移，直到下一个节点的值不再等于这个重复值。注意这里cur本身没有动，因为跨过一整段重复之后，新的cur.next可能又和后面的节点重复了，需要继续处理。

6.2 类似思路的上手迁移

把 “83题 + 82题” 这一对题目吃透，很多链表操作题都能触类旁通：

• LintCode / LeetCode 26题“删除有序数组中的重复项”：虽然数据结构变成了数组，但核心思想一模一样。数组版本更简单，因为可以通过“覆盖”来删除元素，不需要改指针。用快慢指针时，慢指针指向新数组的尾部，快指针负责向后探索，发现新值就搬到前面来。对比链表和数组两种实现，能更加理解“有序”这个概念在两种数据结构里的不同表达方式。

• LeetCode 203“移除链表元素”：删除所有值等于给定值的节点。因为头节点可能被删，也需要dummy node。在写法上，它跟82题很像，但判断条件从cur.next.val == cur.next.next.val变成了cur.next.val == val，本质上都是“检查后继节点是否满足删除条件”。

• LeetCode 21“合并两个有序链表”：合并过程涉及大量next修改操作。写完83题再写21题，你会自然形成一种“指针只能在链表上单向移动”的直觉，这对理解链表合并过程非常有帮助。

6.3 如果面试官追问“链表没有排序怎么办”

这也是一道经典追问。如果链表是有序的，重复元素必然相邻，可以O(1)空间去重；但如果链表无序，相邻元素并不能代表是否重复过，必须用哈希表记录已经出现的值。此时哈希集合是必不可少的，因为不知道当前节点之前有没有出现过同值节点。解法是保存一个prev指针（前一个节点）和一个HashSet<Integer> seen：

class Solution { public ListNode deleteDuplicatesUnsorted(ListNode head) { Set<Integer> seen = new HashSet<>(); ListNode dummy = new ListNode(-1, head); ListNode cur = dummy; while (cur.next != null) { if (seen.contains(cur.next.val)) { cur.next = cur.next.next; } else { seen.add(cur.next.val); cur = cur.next; } } return dummy.next; } }

注意这里仍然用了dummy node，因为无序链表的头节点也可能因为“之前见过相同值”而被删除。这一题的出现，恰好反过来印证了排序条件为83题带来的优化空间。

6.4 相关变体对比表

这张表值得收藏。面试前花三十分钟把这几道题一起过一遍，效果远大于孤立地刷十道题。

7. 手写这道题时最容易翻车的四个细节

这题虽然代码短，但我在实际带新人和模拟面试时，见过太多人在以下四个细节上翻车。专门列出来提醒一下。

细节一：漏掉cur != null判断就直接访问cur.next。空链表是合法的输入之一，没有判空直接写while (cur.next != null)，空链表直接空指针异常。正确做法是while (cur != null && cur.next != null)，短路求值会保证cur.next安全访问。

细节二：相等时用if而不是while处理连续重复。有人在Java代码里写的是：

if (cur.val == cur.next.val) { cur.next = cur.next.next; cur = cur.next; }

这段代码在1 -> 1 -> 1这样的用例上会出错。虽然题目给的是“已排序”，但重复可能连续出现三次甚至更多次。使用if只能跨过一个重复节点，所以必须用while持续判断：只要当前节点和新的下一个节点还相等，就继续跨，直到不同为止。很多同学在自己IDE里跑通1->1->2就觉得万事大吉，忽略了1->1->1->2这种用例。

细节三：搞混“节点相等”和“值相等”。题目要求删除的是“重复的元素”，即val相同的节点。但链表里的节点对象本身是不同的。对ListNode对象使用==，在Java中比较的是引用地址，不是值。判断重复时一定要用cur.val == cur.next.val，而不是cur == cur.next。这个错误在刷题初期特别容易被Python用户忽略——Python里如果你没用val属性比较，直接拿节点对象比较，结果永远是False，因为Python自动调用的__eq__本质上是内存地址比较。

细节四：忽略了返回值的正确性。迭代版本里，有些人习惯用cur作为返回值，这是典型的错误。当遍历结束时，cur已经走到了链表尾部，返回它就等于返回最后一个节点。正确应该是返回原链表的头节点head。一看到“删除”就觉得要新建链表来存储结果的思维，是链表题最大的绊脚石——原地修改指针，头节点不变，就是你想要的结果。

8. 选用迭代解法为主、递归解法为辅的工程考量

很多刷题文章喜欢把两种解法并列，说明思路就完了。但结合实际工程习惯，我想说说我个人的取舍。

日常开发里，如果拿一段业务代码让我分析链表操作，优先选择迭代解法。原因不是递归不好，而是链表的递归思路虽然优美，但存在几个实际工程问题：一是递归调用栈会占用额外空间，在链表数据量较大时可能栈溢出；二是代码可读性看似简洁，但如果维护的人不熟悉递归，理解成本很高；三是递归版本的调试体验比较痛苦——单步调试时要一层一层跳来跳去，远不如迭代版本一顺到底来得好理解。

递归解法更适合什么场景？第一，链表本身就是递归定义的数据结构，某些问题用递归描述会特别清晰，比如反转链表、合并两个有序链表；第二，面试时用来展示对不同解法的理解深度；第三，当链表长度可控、数据量不大时，递归在代码简洁度上胜出。我自己的习惯是“面试先讲递归思路建立直觉，再给迭代解法作为最终实现，并解释两者时空复杂度的差异”，这样既能体现思维层次，又展现工程务实的一面。

工程上还有一个值得说的点是：处理这类链表问题时，尽量不创建新的链表节点，而是在原链表上修改指针。表面上看，新建一个链表也能通过题目，但它会在面试中被扣分——因为题目考察的就是原地修改和指针操作能力，新建链表相当于绕开了考点，也让空间复杂度不再是O(1)。除非题目明确允许复制节点，否则默认都优先原地操作。

9. 从这道题带出的个人刷题心得

最后聊点关于刷题节奏的东西。LeetCode有三千多道题，如果无差别地刷，很快就会进入“题目做了、思路忘了”的循环。我现在带人刷题，特别强调“同类题打包刷”。像83题这样看似基础的题目，它的价值不在于题目本身有多难，而在于它能够连接到多少个变体和面试追问。把83题、82题、21题、206题（反转链表）放在同一周内练习，你会发现它们之间的共性——都是在玩“前后节点指针关系”这个游戏。

我自己的练习方法是这样的：拿到一道链表题，先不急着写代码，拿出一张纸，把链表画出来，手动模拟删除节点的过程。思考顺序是“谁指向谁，改谁的next，最终返回谁”。把这三句话想清楚，再落代码，准确率会高非常多。83题我第一次刷的时候也踩了“相等时cur也向后移动”的坑，后来认真画图模拟1 -> 1 -> 1 -> 2的执行过程，才真正理解为什么相等的分支不能移动cur。

这道题讲完，你会发现它虽然只有十行代码，但背后的“有序性利用”“指针操作原理”“递归分层思路”“变体迁移方法”一整套东西，对于链表类题目的入门来说太值得吃透了。碰到一个看似简单的题，别急着跳过，多问自己一句“如果去掉某个条件，解法会怎么变化”，这道题才算真正刷透了。