链表与树面试核心题解：游乐场里的排队线与组织架构图

可视化演示

展示链表反转与快慢指针操作、二叉树前中后序遍历与BFS层序、二叉搜索树有序性质与平衡操作。切换模式掌握数据结构面试核心题型。

链表结构与类型：认识排队线的四种姿态

游乐场的排队线有几种玩法：最常见的“单人链”里，每个游客只认识自己前面的那一位，想找队尾只能一路问过去，这叫单链表。有的 VIP 通道让游客前后都认识，方便随时换位置，这叫双向链表。还有的花车巡游队伍首尾相接、绕成一个圆圈，这叫循环链表。而在每支队伍最前方，都站着一位穿制服的引导员——他不参与游玩，只负责让“第一个人”更好管理，这就是哨兵节点。

把导游的比喻翻译成代码，链表的最小单元叫“节点”（Node），一个节点包含两块信息：货物区 val 存放数据，指针区 next 存放“下一个人在哪里”。单链表只能从 head 开始单向走，尾节点把 next 指向空 null。双向链表则多一个 prev 指向前一个节点，代价是每个节点多占一份内存。而哨兵节点 dummy 就像引导员站在队首，让“头节点被删除”这类麻烦事不再需要单独开分支处理。

为什么面试爱考链表？因为它的“随机访问”能力很弱。数组按下标能瞬间跳到第 k 个位置，链表却必须从队首开始一步一个脚印。这正是下面的公式要说明的事。

所以面试官看到你写链表第 k 个访问时，期待的从来不是“数组式跳跃”，而是老老实实从头遍历。就像排队引导员从不抄近道，他只会逐个数过去——这种“只能认下一个”的朴素约束，正是链表所有经典题目的出发点。

反转链表家族：给队伍掉头

游乐场广播响起：“所有游客向后转！”原本排在第一位的 1 号想去队尾，只能让整条队伍掉头。掉头的方法很朴素：从队首开始，让每个人松开原来牵着的手，改牵“原来排在自己前面那个人”的手，一个也不能漏。这就是反转链表。

换成程序员的话说，反转链表要做三件事：先记住当前节点的后继（否则一改指向就迷路），再把当前节点的 next 改指向前驱，最后三个指针整体前移。三个指针分别叫 prev（前驱）、cur（当前）、nxt（后继），这是链表面试里最经典的三指针套路。除了整条反转，还有“反转区间”的变体：先走到区间起点，再用同样的三指针逻辑反转区间内部。

迭代版空间无敌；递归版则把“反转 head 之后的整条链”看成子问题，代码短但每层递归都会压栈。递归的直觉是：先让后面的队伍自己掉头，回头再来处理当前节点。链表一长，递归栈就容易爆。

掉头后的队伍里，原来的队首 1 号站到了队尾，头指针指向了 5 号。面试中的“判断回文链表”也是同一招：快慢指针找到中点，反转后半段，再从头逐位比较——相当于让半支队伍掉头，看它是否和另半支一模一样。

合并与双指针：两条队伍合成一条

游乐场两个项目同时散场，两条队伍都按身高从矮到高排好了。工作人员要快速合成一条仍然按身高有序的新队伍：每次只看两条队最前面的游客，谁矮谁先过来。谁先来？永远是对比两队队首。

技术实现上，这题的黄金搭档是“哨兵节点 + 尾指针”。用 dummy 节点做新队伍的假队首，tail 指针始终指向新队伍最后一个人。每轮比较两条链的当前节点，把较小的接在 tail 后面，tail 再前移一步。最后哪条链还有剩余，整体接上即可——就像两条队伍合流时，某条队先走完了，把剩下那条整段搬过来。

与双指针同族的还有快慢指针：慢的每次走 1 步，快的每次走 2 步。在环形跑道上，跑得快的迟早会追上跑得慢的——用这个速度差，可以判断链表是否有环、定位环的入口，还能巧妙地找到链表中点。

就像两条队伍合流时，工作人员只需要记住“下一个该谁”，不需要复印整支队伍的名册。面试官要看到的就是这种“原地、线性”的答案。

二叉树遍历：按规则逛遍组织架构

游乐场的员工架构是一棵树：总经理在顶端，下面分部门经理，经理下面带员工。如果总部要发全园通知，有三种下发顺序：先让领导知道再逐级往下（前序）；先问完左部门、再问领导、再去右部门（中序）；先让基层员工都知道了再向经理汇报（后序）。这三种统称为深度优先遍历。

在树上递归时，每个节点其实会被“经过”三次：进入时一次、左子树回来后一次、右子树回来后一次。前序 = 第一次经过时就记录；中序 = 第二次经过时记录；后序 = 第三次经过时记录。这就是递归序，理解了它，三种遍历只是改一行打印位置的事。层序遍历则像坐电梯，从上到下、从左到右一层层扫过去，需要借助队列实现。

树的遍历几乎是所有树形题——最大深度、子树求和、序列化与反序列化——的地基。很多看起来很难的题，最后都归结为“你选择在递归序的哪一次经过时处理节点”。

就像乐园通知发遍所有员工，无论组织架构多复杂，每个人总会收到且只收到一次。递归序是树递归的灵魂：你不需要死背模板，只需要问自己“这次经过节点时，我该做什么”。

递归进阶与最近公共祖先：帮两人找共同上司

设备部的 7 号员工和演艺部的 4 号员工想找个共同上司审批方案。他们在组织架构图里分别往上走，两条汇报线第一个交汇的节点，就是最近公共祖先（LCA）。注意不是总经理——总经理虽然是共同的上级，但“最近”才是答案。

递归解法的思路建立在子树划分上：从根开始，如果当前节点就是 p 或 q，直接返回；否则分别去左子树、右子树里找。若左子树找到了一个、右子树也找到了一个，说明当前节点就是两条汇报线的分叉点，也就是 LCA；若只有一边找到，就把那一边的答案继续向上传。递归三要素在这里体现得很完整：大问题拆成左右两个子问题、终止条件是遇到空节点或目标节点、返回值用“非空即答案”来统一。

用 h(u) 表示“以 u 为根的子树是否包含 p 或 q”这个布尔值，LCA 的判定就可以写成下面的逻辑式。

面试官一眼就能看出你是否有真懂 LCA：就看你是否明白“两边都命中即分叉点”的判断。这正如在组织架构里，只有当两个人的汇报线在某个节点分叉，那个节点才是他们各自的最近共同上司。

边界与最优解：掉头前先看看队伍空不空

掉头操作开始前，有经验的引导员会先检查三件事：队伍是否空无一人？只有一个人要不要掉？两个人掉头后谁站前面？这些在代码里对应的就是空指针、单节点、双节点这些边界条件。九成链表 bug 都藏在边界里——while cur 忘了判空、nxt 没有先保存、两个节点时头尾指向混乱。

面试最优解还有一条铁律：复杂度先说清，迭代优先于递归。递归虽美，但在链表这种“深度可能等于长度”的结构上，递归栈占用 O(n)，而迭代只需 O(1)。轮到树时则相反：树高决定递归深度，只有树退化成链的时候才需要警惕。

于是面试官眼里最有经验的候选人，落笔前先把空链表、单节点、双节点在脑子里过一遍，落笔时先报复杂度再写代码，写完再用手工例子验证一遍。就像引导员永远先确认“队里还有人、人还认得邻居”，才喊出“向后转”。

AI 应用场景

Python 演示

class ListNode:    def __init__(self, val=0, nxt=None):        self.val = val        self.next = nxt  def build_list(values):    dummy = ListNode()    tail = dummy    for v in values:        tail.next = ListNode(v)        tail = tail.next    return dummy.next  def to_list(head):    out = []    while head:        out.append(head.val)        head = head.next    return out  def reverse_list(head):    prev = None    cur = head    while cur:        nxt = cur.next        cur.next = prev        prev = cur        cur = nxt    return prev  def merge_two(a, b):    dummy = ListNode()    tail = dummy    while a and b:        if a.val <= b.val:            tail.next = a            a = a.next        else:            tail.next = b            b = b.next        tail = tail.next    tail.next = a if a else b    return dummy.next  class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right  def build_sample_tree():    root = TreeNode(3)    root.left = TreeNode(5)    root.right = TreeNode(1)    root.left.left = TreeNode(6)    root.left.right = TreeNode(2)    root.right.left = TreeNode(0)    root.right.right = TreeNode(8)    root.left.right.left = TreeNode(7)    root.left.right.right = TreeNode(4)    return root  def preorder(root):    if root is None:        return []    return [root.val] + preorder(root.left) + preorder(root.right)  def lowest_common_ancestor(root, p, q):    if root is None or root.val in (p, q):        return root    left = lowest_common_ancestor(root.left, p, q)    right = lowest_common_ancestor(root.right, p, q)    if left and right:        return root    return left if left else right  def main():    a = build_list([1, 3, 5])    b = build_list([2, 4, 6])    merged = merge_two(a, b)    print("merge:", to_list(merged))    rev = reverse_list(merged)    print("reverse:", to_list(rev))    root = build_sample_tree()    print("preorder:", preorder(root))    node = lowest_common_ancestor(root, 5, 4)    print("lca(5,4):", node.val if node else None)  if __name__ == "__main__":    main()

1. dummy = ListNode()哨兵节点：给新队伍装一个“假队首”，避免特判头节点，任何情况下 tail 都有东西可接。
2. nxt = cur.next掉头第一步：先记住后面的游客，否则改完指向就找不到他了。
3. cur.next = prev掉头核心一步：让当前游客改牵“原来排在自己前面的人”的手。
4. tail.next = a if a else b某条队先走完时，把另一条剩下的全部接上，像合并队伍时“整段搬移”。
5. if left and right: return rootLCA 的分叉判定：左右子树各命中一个目标，当前节点就是共同上司。

常见误区

面试题