企业官网建设流程全解析

1. 题目是什么：一个被低估的入门关卡

1.1 原题描述与我自己的复述

合并两个有序链表，这个题名听起来平平无奇，但它在我刷题记录里占据了很靠前的位置。题面大概是这样：给定两个按升序排列的单向链表l1和l2，把它们合并成一个新的升序链表，并返回。举个例子，l1 = [1,2,4]，l2 = [1,3,4]，合并后应该是[1,1,2,3,4,4]。

我第一次看到这道题时觉得“不就是比大小吗”，结果动手一写才发现，链表的指针操作和数组的下标操作完全是两种思维。数组里你可以直接用索引移动位置，链表里每一个节点都像一个带把手的箱子，你必须先抓住把手，再顺着绳子走到下一只箱子。绳子是单向的，走过去了就回不来。

题目本身还有一个容易被忽略的隐含设定：两个链表都是升序的。这意味着我们不需要在合并过程中反复回退、比较全局大小，只需要在两列已经排好的数据里做一次线性扫描。换句话说，这题考察的不是聪明，而是你能不能把“两个有序序列合二为一”的过程稳定地翻译成代码。

还有个值得注意的点：题目没有强制要求生成“全新节点”还是“复用原节点”。在实际评测中，原地修改和新建链表往往都能通过。但这会直接影响后续面试官追问时的讨论方向，我在第5部分会专门展开。

1.2 这道题为什么值得反复做

如果你去问一个有经验的面试官“链表入门题推荐哪道”，大概率会得到这道题。原因很简单：它把链表最核心的基本功一网打尽。

第一是遍历。你需要从头到尾访问两个链表，访问过程中还要同时处理两个指针的步进，稍一混乱就容易丢指针。第二是节点之间的链接操作。合并不是把值复制到数组再排序，而是不断修改节点的next指向，把两条链像拉链一样咬合在一起。第三是边界处理。空链表、不同长度、相同值，这些边界如果没处理干净，代码跑在标准例子上没问题，一上大数据量就翻车。

这道题还经常作为更复杂问题的基础组件出现。我后来做合并K个有序链表、链表归并排序时，发现核心的merge函数几乎就是从这道题里原样搬过去的。所以它不是什么“会做就行”的小题，它值得反复练到闭着眼也能写对。

1.3 先把链表基础捋一遍

如果你对链表还不太熟，我建议先花五分钟把下面这个模型过一遍。链表里的每个节点通常长这样：

• val：当前节点存储的值。
• next：指向下一个节点的引用/指针。

最后一个节点的next指向None（或null），表示链到这里结束了。和数组不同，链表在内存里不是连续存放的，它依赖每个节点里的next像项链的链扣一样，把不连续的对象串起来。

合并两个有序链表时，我们本质上是在做一件事：维护两个“待扫描”指针，分别指向两个链表的当前节点，每次选出值更小的那个节点，把它接到结果链表的尾部。这句话听起来简单，但落地为代码时会出现一个经典问题：新链表的头节点到底是谁？因为第一个被选中的节点可能是l1的头，也可能是l2的头。为了不单独写一堆if处理头节点，最省心的做法是引入一个虚拟头节点，也就是业内常说的“哑节点”（dummy node）。这个概念是这道题的第一道分水岭，理解了它，迭代解法基本就通了。

2. 迭代解法：哑节点是这题的第一道分水岭

2.1 思路是怎么来的：归并排序的合并阶段

我当年第一次看到迭代解法的代码时，总觉得这个思路很跳跃——两个指针来回比，为什么就能保证结果有序？后来才知道，这个流程其实就是归并排序里“合并两个有序数组”的那一步，区别只是把数组换成了链表。

归并排序的合并阶段做过什么事？给定两个已经分别排好序的序列，比如[1,2,4]和[1,3,4]，我们用两个下标分别指向各自开头，谁小就把谁放到结果里，然后把那个序列的下标往后挪一步。重复这个过程，直到一边走完，剩下的一边整体接到结果尾部。

链表版本的合并完全复刻这套逻辑，唯一变化的是“下标”变成了“节点指针”，“放到结果里”变成了“把节点接到新链表尾部”。你也可以理解为：我们不是在复制新数据，而只是在重新整理节点之间的绳子，把两条链解开再合并成一条更长的链。这样想，整个代码的意图就清楚多了。

2.2 可复现的 Python 迭代实现

先给一份我日常最常用的 Python 实现。它足够简洁，拆开讲也方便。

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(-1) cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next if l1: cur.next = l1 if l2: cur.next = l2 return dummy.next

逐行拆解一下。

dummy = ListNode(-1)创建了一个值无关紧要的虚拟节点，它不参与结果数据的组织，唯一作用就是给cur提供一个起点。cur相当于“正在构筑的结果链表的尾巴”，一开始指向dummy。

进入while l1 and l2，这个循环条件非常关键：它要求两个链表都还有节点，才会进入比较。只要其中一个已经走空，循环立刻结束，后面统一处理剩下那条链。循环内部比较两个头的值，把较小的节点“接”到cur.next，然后让那个链表的指针往前走一步。不要忘记最后cur = cur.next，这行是让cur始终指向当前结果链表的最后一个节点，漏掉它就是灾难，我在第5部分会详细讲。

循环结束后，两个链表一定有一个已经空了，另一个可能还剩若干节点。因为剩下的那条链本身是有序的，我们直接把它整段接到cur.next后面。这也是代码里两个if所做的事。注意这里不需要再逐个遍历剩下的节点，一次指针赋值就能把整条链接上去。

最后返回dummy.next，因为dummy本身不是真实数据节点，它后面那个节点才是合并后链表的真正头节点。

如果面试官要求用 Java 写，套路完全一致，我贴一份常用版本：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dummy.next; }

C++ 版本也顺手放一下，方便刷题用不同语言的朋友对照：

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur = &dummy; while (l1 && l2) { if (l1->val <= l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 ? l1 : l2; return dummy.next; } };

三种语言的核心逻辑完全一致，真正需要记住的只有三件事：哑节点、双指针循环、剩余链直接拼接。

2.3 复杂度与分析：为什么说它是线性解法

这题的时间复杂度非常好算。两个链表的长度分别为m和n，循环每执行一次，至少会让l1或l2中的一个指针向后移动一步；也就是说，每次循环都消耗掉一个节点。循环最多执行m + n次，之后剩下的那条链用一次指针赋值收尾，不需要额外扫描每个剩余节点。所以总时间复杂度是 O(m + n)（如果两个链表长度合计为 N，也可以写成 O(N)）。

空间复杂度要分两层看。如果只统计算法额外申请的内存，迭代解法只用了dummy这一个节点，以及cur这个指针，都是常数级别，所以额外空间是 O(1)。我见过有人把返回结果链表的节点也算作空间开销，但那些节点原本就是输入的一部分，我们只是在重新组织它们的next指向，并没有“新建”一个和链表等长的数据副本。

你可能会问：为什么循环的次数不是“比较的次数”而是“节点消耗的次数”？因为每次比较只会消耗l1或l2中的一个节点，就算一边先耗尽，另一边的剩余节点也不需要任何进一步比较，直接整段拼接即可。这就是有序结构的红利：它让你不必回到序列开头重新扫描，合并过程是单调推进的。

3. 递归解法：让函数的返回值替你做合并

3.1 递归拆解：每次只比两个头节点

迭代解法是把合并过程拆成“走一步，接一个节点”，递归解法则是把问题拆成“当前这一步选谁，剩下的交给函数自己”。两种思路殊途同归，但递归版写出来往往更短，也更像一道数学归纳法。

我们先明确合并问题的定义：给定两个有序链表l1和l2，返回合并后的链表头。那么站在“当下”这个时刻，我们要做的事情只有一件：比较两个链表的头节点，选出值更小的那个作为结果链表的头。选出来的那个头节点，它后面应该接什么？答案是：接“剩余的两个链表继续合并”的结果。

举个例子。如果l1.val = 1，l2.val = 3，那么合并结果的头必须是l1的那个节点。接下来要处理的问题变成：合并l1.next和l2。换句话说，l1.next应该被赋值为“合并l1.next和l2的结果”。所谓的递归，就是把这个相同的逻辑一层一层传下去，直到某一个链表为空。

递归基也很自然：如果l1已经为空，剩下的结果就是l2；如果l2已经为空，剩下的结果就是l1。空链表是递归结束的出口，这也正好对应了真实世界里的物理动作——一条链已经用完了，就把另一整条链“甩”回去。

3.2 递归代码与调用栈推演

下面是完整的递归实现：

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode: if not l1: return l2 if not l2: return l1 if l1.val < l2.val: l1.next = mergeTwoLists(l1.next, l2) return l1 else: l2.next = mergeTwoLists(l1, l2.next) return l2

先看两个递归基。if not l1排除了l1为空的情况；if not l2处理l2为空。如果两个都为空，第一个条件先触发，返回l2，而l2此时也是None，结果正确。

再看比较部分。我用的是<，而不是<=。两个写法在本题通常都能通过，但用<时，如果两个头节点值相等，优先保留l2的节点；用<=时会优先保留l1的节点。这其实涉及稳定性：如果两个链表里的节点除了val之外还带着其他附加数据，我们往往希望保持它们的相对顺序不变。虽然题目没有明说，但这在面试里是个可以主动讨论的加分细节。

函数内部看起来像是在原地修改链表：l1.next = mergeTwoLists(l1.next, l2)，实际上它在“选中的较小节点”和“后续合并结果”之间补上了链接。递归函数一层层返回时，链接会从最深处一路倒着接回来，最终返回的l1或l2就是整个合并结果的头节点。

我拿一个小例子推演调用栈。假设l1 = [1,2]，l2 = [1,3]。执行过程大致如下：

1. 比较两个头节点，1 == 1，走else分支，于是l2.next = mergeTwoLists(l1, l2.next)，等递归返回后，return l2。
2. 现在处理mergeTwoLists([1,2], [3])。比较 1 和 3，走if分支，l1.next = mergeTwoLists([2], [3])，等递归返回后，return l1。
3. 继续处理mergeTwoLists([2], [3])。2 小于 3，走if分支，l1.next = mergeTwoLists(None, [3])，返回后return l1。
4. mergeTwoLists(None, [3])触发递归基if not l1，直接返回[3]。
5. 逐层返回时，链接依次变为：2 后面接 3，1 后面接 2，最外层l2节点后面接[1,2,3]整条链。

最终得到[1,1,2,3]，顺序没有问题。你在脑内过一遍这个栈，就会明白为什么递归代码不需要显式的dummy节点——头节点的选择问题被“返回值就是合并结果头”这句话优雅地化解了。

3.3 递归和迭代怎么选

两种解法的优缺点非常鲜明，整理成表格更方便对比：

在真正的面试环境中，我更推荐先冷静地把迭代解法写对，因为它的空间复杂度更好，也不受递归深度限制。但如果面试官追问“还有没有其他写法”，再写递归版会显得你对这道题的理解不止一层。我在实际刷题中见过的最优解基本都是迭代，而递归更像是用来验证思维清不清楚的“加分项”。

还有个实用的判断标准：如果题目允许修改输入链表，递归版会显得很自然；如果强调“不得修改原链表”，那无论迭代还是递归，都要在接到节点时新建副本，不能直接改next。

4. 边界条件与测试用例：让代码经受住拷问

4.1 空链表：最常见的边界雷区

很多人在写代码前都会忘记一件事：链表是可能为空的。题目输入不是非得有两个正经链表，l1和l2都可能直接指向None。

假如我们写了一个没有空判断的朴素版本，比如：

while l1 and l2: ...

这个版本已经把空链表的情况包含在循环条件里了，所以它其实不会直接爆炸。但如果你把循环条件写成while l1 or l2，再在循环体里比较l1.val和l2.val，那就麻烦了：一旦某个链表为空，访问.val直接抛空指针异常。

更隐蔽的问题出现在“一个为空，另一个不为空”时。比如l1 = None，l2 = [1,2,3]，迭代代码中while l1 and l2直接不进入，然后走到末尾的if l2: cur.next = l2，把整条l2接回去，结果是正确的。但这个行为依赖的是收尾逻辑写得完整。如果只写了while循环忘了收尾，返回值就只有dummy.next，可能变成None，白白丢掉整条链表。

所以要养成的习惯是：把“两个都空”“一个空”“两个都不空”这三种情况分别脑内过一遍，再提交代码。尤其是空链表判断，很多边界错误都发生在这里。

4.2 链表长度不一致时的收尾逻辑

当两个链表长度不同，较短的链表会率先耗尽。此时循环退出，另一个链表可能还剩不少节点。这个收尾动作，是链表合并里最体现“经验”的地方。

我第一次自己写的时候，收尾写成了：

while l1: ... while l2: ...

意思是把剩余节点逐个接上去。这当然没错，但很啰嗦。后来我看到一个更聪明的写法：cur.next = l1 if l1 else l2，一行搞定。为什么能这么写？因为剩余的那条链表本身已经是有序的，它内部的结构无需任何改动，直接把整段链接到cur.next即可。你不欠它任何额外的“逐节点处理”。

理解这行代码的关键在于：cur指向当前结果链表的最后一个节点，而l1或l2中那个还没走空的指针，指向的正是“那条链剩余部分的头”。把cur.next指向它，就像把一段现成的链条卡扣接上去，一步到位。

4.3 我的测试用例清单

我刷这道题时会准备一组测试用例，专门覆盖容易出错的方向。你可以直接抄去用：

用例3是最常规的“拉链式”交叉；用例4和5覆盖长度不对称；用例6专门测相等值时的稳定性，看代码是否保持链内原有顺序；用例7则测负数场景，防止你在比较逻辑里写死“第一个数大于等于0”之类的错误假设。每次面试前我都会把这些用例在草稿纸上快速跑一遍，比空想可靠得多。

5. 我在反复提交中踩过的坑

5.1 漏掉 cur = cur.next 导致的死循环

这道题最大的坑，不是看不懂思路，而是看懂了思路却漏写一行关键代码。我第一次独立写迭代解法时，循环体大概是这样的：

while l1 and l2: if l1.val < l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next # 忘了写 cur = cur.next

当时我觉得逻辑天衣无缝：每次比较、接节点、移动输入指针，不是挺齐的吗？结果一跑，发现返回结果乱七八糟，而且链表可能直接变成死循环。

原因很直接。cur没有移动，它始终指向dummy。下一轮循环又会执行cur.next = ...，把上一轮刚接好的节点覆盖掉。最终结果链表的尾部不是推进到最后节点，而是一直停留在起点附近，数据大量丢失。更糟的情况是，如果你把cur.next又指回链表中某个已有节点，就可能形成环。

我后来总结出一个检查习惯：写迭代链表题时，每接一个新节点，都要问自己“我是不是让当前尾巴指针往后走了一步”。这个动作在数组归并里对应的是“结果数组下标加一”，在链表里就是cur = cur.next。它和更新输入指针是两回事，不能混为一谈。

为了排查这类问题，可以写一个简单的打印链表函数：

def print_list(head): while head: print(head.val, end=" -> ") head = head.next print("None")

在每次cur.next = ...之后打印整条链，你会很直观地看到哪里断了、哪里多了环。我靠这招解决过不只这一个链表 bug。

5.2 递归里忘记改 next 造成的环

迭代版容易漏指针步进，递归版也有自己的幺蛾子。最经典的错误是：比较完节点后，直接return l1或return l2，忘了设置较小节点的next。

比如写成：

if l1.val < l2.val: return l1 else: return l2

这会导致两个链表都只保留头节点，后面的全部丢失。更隐蔽的错误是递归参数写错，比如：

l1.next = mergeTwoLists(l1, l2.next)

这里本意应该是合并l1.next和l2，结果把l1自己又传进去了。因为输入链表没有减少，递归永远不会结束，最终栈溢出。而且由于l1.next被一个尚未返回的结果赋值，整个链表结构可能在递归推进过程中先被破坏，形成环。

我的排查经验是：递归链表题的每次next赋值，都可以用“下一次函数调用时，输入参数一定比当前更短”来校验。如果传进去的链表和当前的一样长，就要警觉了。

另外要注意，递归版的空间复杂度是 O(m + n)。两个链表都特别长时（比如几万个节点），即使逻辑完全正确，也可能因为调用栈太深直接崩溃。我在某个在线评测平台上见过长度为几万节点的极端用例，递归版虽然能过，但耗时明显更高；在真实项目的代码审查里，这种写法也可能被要求改成迭代。

5.3 一次通过的小技巧：画图与打印链表

很多读者会问我：为什么有人能一次性写对链表题？我的回答是：大多数人在动手前画了图。

具体画法很简单。第一步，画两个初始链表，标出l1、l2、dummy、cur四个关键位置。第二步，模拟一次循环，把被选中的节点用箭头接到cur.next，再画出移动后的l1或l2，以及移动后的cur。第三步，一直画到循环结束，看看收尾逻辑应该怎么接。

这三步画完，代码几乎是照着图翻译。我在后面做合并K个链表之类更复杂的问题时，用的也是同样的方法。链表题最大的敌人不是看不懂题，而是大脑里对指针状态的想象不够清晰。画图本质上是把你脑子里的“想象”变成看得见的“状态”。

打印链表则是验证阶段的利器。你可以提前写好一个print_list，然后在关键步骤之间打印当前链表状态。尤其在排查死循环时，打印次数会明显暴露问题位置——如果同一状态被打印了两次，说明代码里出现了环。

6. 一道题带出的延伸：合并K个链表与归并排序

6.1 合并K个有序链表的两种思路

这道题最直接的延伸，是把“两个”换成“K个”：给定 K 个有序链表，把它们全部合并成一个有序链表。思路基本有两种。

第一种是“两两合并”。把所有链表顺序遍历，先用第一个和第二个合并，结果再和第三个合并，依此类推。这种做法的总时间复杂度是 O(KN)，其中 N 是最终链表的总节点数。如果 K 比较小，代码最简单，但链表数量一多，前面已经合并好的链表会被反复扫描，效率不高。

第二种是“分治合并”。把 K 个链表对半分，各自递归合并，再把两个结果合并。时间复杂度降到 O(N log K)。这个思路和归并排序如出一辙，K 较大时优势很明显。

除了这两种，还有一个更“堆”的做法：维护一个大小为 K 的最小堆，每次从堆里弹出值最小的节点，接到结果链表尾部，然后把这个节点的next压入堆。时间复杂度同样是 O(N log K)，但实现起来需要自己写比较器，在面试中属于进阶方案。

无论是分治还是堆，你都会发现核心的merge逻辑和“合并两个有序链表”完全一致。所以这道看似基础的小题，其实是整个链表合并体系的“根节点”。

6.2 链表归并排序：merge 函数是拆不掉的骨架

链表排序的经典方案就是归并排序，因为链表不方便像数组那样随机访问，快排的分区操作在链表上写起来很别扭，而归并排序只需要“找中点、递归排序、合并”三个动作，每个动作都能用链表指针完成。

找链表中点常用快慢指针：慢指针每次走一步，快指针每次走两步，快指针到末尾时，慢指针正好在中点。找到中点后，把链表从中间断开成两半，分别递归排序，最后调用我们这道题的mergeTwoLists把两个有序子链合成一条。

所以你要是把“合并两个有序链表”练熟了，链表归并排序相当于只多了一个“找中点”函数。很多标着“中等难度”的链表排序题，核心难点其实就藏在这个 merge 里。反过来做一遍链表排序，你对这道题的掌握也会进一步加深。

6.3 面试追问与可变种练习

面试官聊完这道题之后，常见的追问大概有这么几类。

一是稳定性。如果两个链表里有相等的值，合并后它们的相对顺序还能不能保持？迭代版用<=、递归版用<，不同的选择会影响稳定性，面试官可能让你明确说出选择依据。

二是空间复杂度。能不能写出 O(1) 额外空间的递归版本？答案是不能，因为递归本身需要调用栈。想做到 O(1)，就必须用迭代。

三是原地修改问题。合并后原来的链表结构变了，如果有其他代码仍然持有原链表的头节点，可能会出问题。面试官会问：如果需要保留原链表，怎么做？答案是遍历时新建节点副本，代价是空间复杂度升到 O(m + n)。

可变种练习我也推荐几个：合并两个降序链表、合并后要求逆序输出、两个链表中可能含有环、合并后要求去重。这些变体都是在“合并两个有序链表”这个骨架上加料，先把这个基础题打牢，再去做变体会轻松得多。

我自己把这道题刷了三轮。第一轮只看懂迭代解法，第二轮才彻底理解递归，第三轮是面试前重新自己推导复杂度。过程中最大的转变，是意识到链表题考的不是聪明，而是能不能把一个指针状态的变化老老实实追踪清楚。如果你是第一次接触这道题，我的建议是先别急着写代码，拿两个链表画一遍合并过程：先画两个链表的初始状态，再画中间某一步的状态，最后画结束状态。这个习惯帮我避开了大量低级错误，也让我在后续合并K个链表和链表排序上省了很多力气。