链表（单/双/循环）实战指南

CH-01-03-002·约 19 分钟·计算机基础·更新 2026-08-10

假设你是一名站台调度员，面前停着一列永远不摘开的货运火车。派车单上只写了第一节车厢的位置，想知道第 8 节装的是什么，你必须从车头开始，一节一节爬过去——因为每节车厢只通过一个挂钩牵住后面那节车厢。这个“车厢 + 挂钩 + 派车单”的模型，就是链表最朴素的样子。它的优点是：想在中间挂一节新车厢，只需要解开两个挂钩，不用挪动整列车；缺点也很明显：想随机找某节车厢，只能老老实实从头走。后来，工程师们又发明了前后都能挂钩的双链表，以及首尾相接、可以无限绕圈的循环链表。本文就用这趟“调度列车”，把三种链表、复杂度分析和工程实战一次讲透。

岗位关联

链表是数据结构的第一堂“调度课”。从缓存系统、编辑器撤销栈，到 AI 训练数据的环形缓冲，处处都有它在背后牵线搭桥。理解链表，是 AI 工程师从“会调库”走向“能设计数据管道”的起点。

可视化演示
链表本质：节点与挂钩
双链结构：前后双挂钩
循环链表：闭合的环形铁路
复杂度对比：时间账本
工程实战：调度手册
调优避坑：老调度员的口诀
AI 应用场景
Python 演示
常见误区
面试题

可视化演示

展示单链表遍历插入操作(O(n)/O(1))、双向链表前后指针导航与循环链表哨兵节点结构、链表与数组内存布局及性能对比。

本节配有交互动效（进入视口后自动加载，约 3KB）。

单链表遍历与插入操作 HEAD指针指向首节点，next串联后续节点 NEW节点插入：修改前后next指针O(1) insert: p.next=new; new.next=next; O(1) 单链表只支持单向遍历，查找O(n)，已知位置插入删除O(1)。

链表本质：节点与挂钩

调度员小陈刚入职时，师傅只交给他一张派车单，上面写着“1 号车厢在 3 号月台”。他走到 1 号车厢，发现它的尾部挂钩上挂着 2 号车厢；走到 2 号车厢，又看到 3 号车厢。整列火车就是靠这种“一节扣一节”的方式连起来的。要在第 4 节后加一节新车厢，他只需要松开第 4 节尾部的挂钩、挂上新车厢，再把新车厢的挂钩挂上第 5 节——整列车纹丝不动。这就是链表最核心的直觉。

在计算机里，每节“车厢”被称为节点（Node），货物就是节点的值，尾部挂钩就是 next 指针。派车单就是头指针 head，它只告诉你第一个节点在哪里。因为每个节点只知道“下一个是谁”，所以想找第 k 个节点，只能让指针从 head 开始，逐个跳转 k-1 次。这种只能单向前进的结构，叫作单链表。

单链表的插入和删除本质上只有两三行代码：插入时先让新节点指向后驱，再让前驱指向新节点；删除时直接让前驱的 next 跳过目标节点。工程上为了简化边界判断，常常在真正的头节点前放一个不存数据的“哨兵头节点”，就像月台上放一节空引导车厢，让“空链表”和“删除第一个节点”这些特殊情况都不再特殊。

小陈后来发现，单链表“重查找、轻增删”的性格非常鲜明：只要你知道车厢在哪，挂卸都极快；但如果你连位置都要现找，整趟列车的长度就变成了代价。

\displaystyle T(n) = \frac{1}{n}\sum_{i=1}^{n} i\,t_{\text{hop}}= \frac{n+1}{2}\,t_{\text{hop}} = O(n)

通俗解释：在 n 节车厢的列车里随机找一件货，平均要跳过大约一半的车厢，所以查找耗时随列车长度线性增长。

定义总开销设 t_hop 是“跳过一个挂钩”的时间，在长度为 n 的单链表中，找第 i 个节点需要 i 次跳转，总查找时间为所有位置的平均值。
$\displaystyle T(n) = \frac{1}{n}\sum_{i=1}^{n} i\,t_{\text{hop}}$
计算求和结果从 1 加到 n 的等差数列和为 n(n+1)/2，这是“把所有车厢都找一遍”的累计跳转次数。
$\displaystyle \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
取平均位置用总和除以 n，得到随机查找平均需要 (n+1)/2 次跳转。
$\displaystyle \frac{1}{n}\times \frac{n(n+1)}{2} = \frac{n+1}{2}$
表达增长趋势当 n 趋于无穷时，系数 1/2 和常数项都可忽略，复杂度记为 O(n)。
$\displaystyle \frac{n+1}{2}\,t_{\text{hop}} = O(n)$

双链结构：前后双挂钩

单链表虽然灵活，却有个让调度员头疼的事：要是走过头，他必须从车头重新走一遍。于是机务段改造了车厢，让每节车厢前后各装一个挂钩——前面的挂钩勾住上一节，后面的挂钩勾住下一节。小陈现在既可以从车头往后走，也可以从车尾往前倒，甚至能从中间直接倒车。这就是双向链表。

双向链表的节点里除了值，还有两个指针：prev 指向前驱节点，next 指向后继节点。多一个指针带来的最直接好处是：已知某个节点 p，删除 p 时不再需要遍历找它的前驱，直接改写 p.prev.next 和 p.next.prev 两条指针即可，时间复杂度从单链表的 O(n) 降到 O(1)。如果再用 tail 指针记住最后一节车厢，那么在尾部插入也稳定是 O(1)，不用每次从头跑到尾。

代价当然也有：每节车厢要多挂一块“前车车牌”，也就是每个节点多存一个指针。当节点数量达到百万级时，多出来的内存非常可观。所以双链表并不是单链表的“升级版”，而是用空间换时间、用内存买灵活性的方案，就像豪华列车多装了倒车雷达，但每节车厢也更重、更贵。

小陈的调度手册上记着：如果任务大多是“从两端装卸货、频繁撤销操作”，就派双链表上场；如果只是顺序扫描，双链表多出来的 prev 反而成了包袱。

\displaystyle T_{\text{double}}(k, n) = \min(k,\ n-k) \times t_{\text{hop}}

通俗解释：双向链表让调度员可以选择“从哪头走更近”，最坏情况从原来的走完整列车，变成最多走半列车。

定义两个方向的距离目标是第 k 节车厢，从头部出发需跳 k 次，从尾部出发需跳 n-k 次。
$\displaystyle T_{\text{head}} = k\,t_{\text{hop}},\qquad T_{\text{tail}} = (n-k)\,t_{\text{hop}}$
取更近的一侧双向链表真正强大的地方是可以在两个方向中选择较优者。
$\displaystyle \min(k,\ n-k)$
乘以单次跳转成本总时间等于跳转次数乘以每跳一次的时间 t_hop。
$\displaystyle T_{\text{double}}(k, n) = \min(k,\ n-k) \times t_{\text{hop}}$
对比单链表单链表只能取 k，期望值约 n/2；双链表取 min 后，期望值下降到约 n/4。
$\displaystyle E[T_{\text{double}}] \approx \frac{n}{4}\,t_{\text{hop}} < \frac{n}{2}\,t_{\text{hop}} = E[T_{\text{single}}]$

循环链表：闭合的环形铁路

小陈的站台旁有一条环线铁路，列车的最后一节车厢不是接上空气，而是通过一个特制挂钩绕回第一节车厢。这样一来，列车不再有“终点”，只要调度员愿意，它可以一圈一圈永远跑下去。这种首尾相接的结构，就是循环链表。

循环链表的核心差别只有一处：普通单链表的尾结点 next 指向 null，而循环链表的尾结点 next 指向 head。这个小小的闭环让很多“绕圈”问题变得自然：比如操作系统里的时间片轮转、音视频播放器的环形缓冲区，还有著名的约瑟夫问题——一群人围成一圈报数，数到 k 的人出列，再从下一个人继续报数，直到剩最后一人。

用循环链表模拟约瑟夫问题非常直观：节点围成一个环，每次沿 next 走 k 步，删除当前节点，再从下一个节点继续。这种模拟思路的时间复杂度是 O(nk)，因为要删除 n-1 个人，每次都要数 k 步。如果数据规模很大，还可以用数学递推直接算出存活者编号，连链表都不用建。

小陈在笔记上画了一个圆环：循环链表最怕的不是“没有终点”，而是“忘了设终点”。环形列车虽然能一直跑，但调度员如果忘记数圈数，就会永远困在环上。

\displaystyle J(n,k) = \begin{cases} 0 & n=1 \\ (J(n-1,k) + k) \bmod n & n>1 \end{cases}

通俗解释：约瑟夫递推式把“n 个人报数”拆解成“先解决 n-1 个人的子问题，再把结果平移 k 个座位”，绕圈的本质被浓缩成一个取模运算。

基准情况只剩 1 个人时，他的编号是 0，所以 J(1,k)=0。
$\displaystyle J(1,k) = 0$
递归地缩小规模n 个人删掉第一个出列者后，剩下 n-1 个人继续报数，子问题的答案是 J(n-1,k)。
$\displaystyle J(n-1,k)$
编号平移子问题中的“第 0 号”对应原问题里的第 k 号，所以要加上 k。
$\displaystyle J(n-1,k) + k$
取模绕圈因为编号从 0 到 n-1 循环，加 k 后可能超过 n-1，所以对 n 取模，模拟“数到末尾绕回开头”。
$\displaystyle (J(n-1,k) + k) \bmod n$

复杂度对比：时间账本

调度室里贴着一张“成本账本”，小陈每次选型前都要先算一笔账：这趟任务到底是要频繁“按位置找货”，还是要频繁“在中间加货”？数组就像一排固定编号的仓库，门牌号连续，报出编号就能直接冲到对应仓库；链表像刚才那列火车，只有走到才能知道下一节在哪。两者的时间账截然不同。

数组在内存中是连续空间，所以按下标随机访问是 O(1)——CPU 只要做一次地址计算。链表没有下标，随机访问必须从头跳指针，是 O(n)。但在“已知位置的插入和删除”上，数组要搬动后面的所有元素，平均 O(n)；链表只需要改两三个指针，是 O(1)。空间上，数组紧凑但可能预分配浪费，链表按需创建但每个节点都要背负 next/prev 指针。

所以不存在“谁一定更好”的答案。业务里如果是“写入多、读得少”的日志队列，链表更合适；如果是“读多写少”的配置表，数组完胜。这也是为什么每个老调度员手里都有一本账：复杂度分析不是为了背 O(1)、O(n) 的记号，而是为了在真实场景里做出性价比最高的选择。

小陈把这张账本贴在调度室墙上：复杂度不是考试分数，而是选型时的“试算表”。他常说，没有万能的车厢，只有算明白的账。

\displaystyle \begin{array}{c|c|c}& \text{数组} & \text{链表} \\\hline\text{随机访问} & O(1) & O(n) \\\text{已知位置插入} & O(n) & O(1) \\\text{内存布局} & \text{连续} & \text{分散}\end{array}

通俗解释：数组靠门牌号直达，链表靠挂钩链式追踪；数组搬家贵，链表找路贵。

随机访问对比数组通过下标计算地址一步到位，链表必须从 head 逐个跳转。
$\displaystyle T_{\text{下标访问}} = O(1),\qquad T_{\text{链表随机访问}} = O(n)$
已知位置插入对比数组插入需要把后续元素整体后移，链表只需改写前后节点的指针。
$\displaystyle T_{\text{数组插入}} = O(n),\qquad T_{\text{链表插入}} = O(1)$
内存布局对比数组占用一块连续内存，链表节点散落在堆的不同地址。
$\displaystyle \text{数组偏序整齐},\qquad \text{链表指针跳跃}$
选型决策当增删操作远多于随机读时，链表的时间账更划算；当读请求占绝对主导时，数组胜出。

工程实战：调度手册

真正的铁路公司不会只买一种车厢，小陈的调度手册里记录了三种最常用的“车型”。第一种是 LRU 缓存——最近最少使用淘汰策略。它用哈希表快速定位节点，用双向链表维护访问顺序：每次访问就把对应节点挪到链表头部，容量满了就删掉尾部节点。哈希表负责“找得快”，双链表负责“排得顺”，两者一组合，读写都是 O(1)。

第二种是编辑器里的撤销重做（undo/redo）历史。每做一次操作就生成一个新节点接到链表尾部，当前状态用一个指针标记；撤销时指针前移，重做时指针后移。如果用户做了新操作，就从当前指针处切断后面的“未来历史”，这正是双向链表“前驱与后继”最贴合的场景。

第三种是 AI 训练中的环形缓冲区。模型训练时，数据读取线程和生产线程速度不同，可以用循环链表把数据块串成环：写满一圈就覆盖最旧的数据，读指针和写指针永远在环上追跑。它避免了频繁申请和释放内存，也让“流式数据”有了天然的轮转语义。无论是 LRU、撤销栈还是环形缓冲，背后都是同一句话：用链表的指针灵活性，去匹配现实中“增删频繁、顺序流动、边界模糊”的访问模式。

小陈的手册结尾写着：工程里的好结构从来不是“用更炫的算法”，而是“用最匹配的零件”。哈希表管定位、双链表管顺序、环形链表管轮转，各司其职。

\displaystyle T_{\text{LRU}} = T_{\text{hash}} + T_{\text{list}} = O(1) + O(1) = O(1)

通俗解释：哈希表让调度员瞬间找到车厢，双链表让车厢秒级换位置，合起来就是“找得快、挪得也快”。

哈希定位通过 key 在哈希表中查找链表节点，平均时间复杂度为 O(1)。
$\displaystyle T_{\text{hash}} = O(1)$
链表重排把命中的节点从当前位置摘下来、移到链表头部，只修改少量指针。
$\displaystyle T_{\text{list}} = O(1)$
相加仍为常数两个 O(1) 相加，整体依然是常数时间。
$\displaystyle O(1) + O(1) = O(1)$
容量淘汰缓存满时删除链表尾节点，同样只需要双链表指针操作和哈希删除。
$\displaystyle T_{\text{evict}} = O(1)$

调优避坑：老调度员的口诀

小陈的笔记本里积攒了许多“事故案例”。第一个事故叫“断链顺序”：删除单链表的节点 p 时，新手常先把 p 的 next 改了，结果前驱节点还指着 p，链表断成两截。正确做法是先让前驱的 next 跳过后驱，再处理节点本身——就像先挂好新挂钩，再解开旧挂钩，车厢才不会脱轨。

第二个事故叫“死循环排查”：循环链表里如果没有终止条件，遍历程序会永远绕圈。老调度员的经验是：判断是否到表尾看 cur.next == head，判断是否绕完一圈看 cur == head。尤其在多线程并发操作链表时，指针被并发修改还可能造成更隐蔽的环，所以要借助快慢指针或加锁来排查。

第三个事故和 CPU 缓存有关。链表节点在内存里通常分散分配，遍历时每次都要跳到一个新地址，CPU 缓存命中率远低于数组的顺序访问。调优手段包括：用内存池一次性分配多个节点、把常用节点尽量放在相邻地址，或者在链表变成千万级且以遍历为主时，干脆改用数组。小陈的口诀因此是四句话：先断后链防丢失，绕圈计数设终点；池化节点提局部，读写比例定乾坤。

小陈最后在笔记本扉页写下：复杂度解决“会不会慢”，缓存问题解决“实际有多慢”。真正的调优，是在算清理论复杂度后，再用工程手段把常数项压到最低。

\displaystyle T_{\text{array}} = n\,t_{\text{seq}},\qquad T_{\text{list}} = n\,(t_{\text{hop}} + t_{\text{miss}})

通俗解释：数组遍历像沿着一排连续的货架走，每步都踩在缓存上；链表遍历像在仓库里按纸条地址到处找，每跳一步都可能重新开门。

数组顺序访问连续内存让 CPU 一次预取一排数据，每个元素近似一个固定的小开销 t_seq。
$\displaystyle T_{\text{array}} = n\,t_{\text{seq}}$
链表指针跳转每访问一个节点都要先读出 next 指针，再跳到下一个地址，开销含 t_hop。
$\displaystyle T_{\text{hop}} = n\,t_{\text{hop}}$
缓存未命中惩罚节点分散时，每次跳转都可能触发缓存未命中，额外付出 t_miss。
$\displaystyle T_{\text{miss}} = n\,t_{\text{miss}}$
总成本对比链表总开销是两者之和，当 n 很大时，t_miss 往往远大于 t_seq，差距被放大。
$\displaystyle n\,(t_{\text{hop}} + t_{\text{miss}}) \gg n\,t_{\text{seq}}$

AI 应用场景

LLM 推理服务中的 LRU 缓存

阶段：推理服务优化

解决的问题：大模型推理时，相同 prompt 的 KV Cache 或中间结果会被重复请求。用哈希表加双向链表实现 LRU，可以让“最热门的对话”永远留在缓存头部，冷数据自动淘汰。相比传统数组实现，插入和淘汰都是 O(1)，不会因为缓存滚动而整体搬移。

具体案例：某 AI 客服系统每天处理大量相似问题。把用户 query 哈希后映射到双向链表节点，每次命中就把节点移到头部；内存达到上限时删除尾部节点。实测缓存命中率提升 18%，平均首 token 延迟降低 35%。

训练数据流式加载的环形缓冲区

阶段：数据预处理与流式加载

解决的问题：数据读取线程持续把样本写入队列，训练线程持续消费。如果用数组实现固定队列，写满后需要搬移数据；用循环链表实现环形缓冲区，写指针绕回头部即可覆盖旧数据，天然支持“滑动窗口”语义。

具体案例：某推荐系统训练管道用循环链表组织用户行为序列，窗口大小为 1024。每条新行为覆盖最旧行为，模型在线学习时始终看到最近的数据分布，无需每次重建整个序列。

大模型对话历史的双向链表管理

阶段：交互状态管理

解决的问题：多轮对话中用户可能“撤销上一条消息”或“回退到某个历史节点”。双向链表让当前对话位置自由前后移动：一条新回复插入后，后续的“未来消息”自动从此处截断。相比用数组拼接字符串，这种结构新增、回退、截断都只改指针。

具体案例：某 AI 编程助手维护代码修改历史，用户可以用“撤销/重做”在链表中来回移动；当用户产生新修改时，从当前位置切断重做链，避免“未来的编辑”污染当前状态。

Python 演示

python36 行

class Node:    def __init__(self, value):        self.value = value        self.next = None  def build_circular_list(n):    head = Node(1)    cur = head    for i in range(2, n + 1):        cur.next = Node(i)        cur = cur.next    cur.next = head    return head  def josephus(n, k):    head = build_circular_list(n)    prev = head    while prev.next != head:        prev = prev.next    cur = head    step = 0    while cur.next != cur:        step += 1        if step == k:            prev.next = cur.next            step = 0        else:            prev = cur        cur = cur.next    return cur.value  if __name__ == "__main__":    print(josephus(7, 3))

目的：用循环链表模拟约瑟夫问题，演示“尾结点 next 指向 head”如何让报数绕圈变得自然。

class Node:定义链表车厢：value 是货物，next 是尾部挂钩。
cur.next = head把最后一节车厢的挂钩接回第一节，形成循环链表。
while prev.next != head:找到尾结点，让 prev 站在链尾，方便后续删除。
while cur.next != cur:循环直到只剩一节车厢。
step == k数到第 k 个人，执行删除：让前驱的 next 跳过当前节点。
prev = cur没数到 k 时，前驱指针跟着当前节点前进。
cur = cur.next无论是否删除，当前指针都移向下一个节点，继续报数。

常见误区

误区我听别人说链表插入是 O(1)，所以只要频繁增删一律用链表，数组扩容又慢又浪费，能不用就不用。

正解链表插入 O(1) 的前提是“你已经站在目标节点旁边”。实际工程里往往要先从头遍历找到插入位置，定位成本是 O(n)。就像调度员解挂钩很快，但他得先走过整列车找到目标车厢。数组在“读多写少”的场景下，随机访问 O(1) 加上 CPU 缓存友好，依然比链表更实用。

为何常见：初学者只记住了结论里的 O(1)，忽略了它依赖“已知位置”这个条件，把局部操作复杂度当成了整体操作复杂度。

误区删除节点 p 不就是把 p 丢掉吗？我直接写 p = p.next 为什么链表没变？明明代码执行了呀。

正解p 只是链表里的一个指针副本，修改 p 只是让这个局部变量换了个指向，前一个节点的 next 依然指着 p。要让链表真正跳过 p，必须拿到前驱 prev，把 prev.next 指向 p.next。除非使用“复制后驱”的技巧，但那个技巧不适用于尾节点。

为何常见：把“指针变量”和“节点对象”混为一谈，是初学指针和链表时最常见的认知错位。

误区循环链表首尾相连，我沿着 next 一直走迟早回到原地，所以遍历时不需要判断边界，反正不会越界。

正解循环链表只是尾结点的 next 不再为 null，遍历依然要设置终止条件，比如记录已访问节点数或判断 cur == head。否则程序会像环线列车一样永远绕圈，最终内存被无限增长的数据撑爆。

为何常见：把“循环”误解为“天然安全”，反而忽略了循环结构是死循环的高发地带。

误区数组要一次性分配一大块内存，链表用多少分配多少，所以链表肯定更省空间。

正解链表每个节点都要额外存 next 指针，双链表还要存 prev，百万节点就是数百万个额外指针。数组虽然可能预分配有浪费，但它没有指针包袱、内存连续。准确说法是：链表按需扩容不搬移，数组连续紧凑但扩容要复制。

为何常见：只看到“按需分配”的一面，忽略了每个节点都要背负指针字段的固定开销。

面试题

Q1. 已知单链表中的某个节点 p，在 p 后面插入一个新节点的时间复杂度是多少？

单选题 · easy

A.O(1)← 正确答案
B.O(n)
C.O(log n)
D.O(n log n)

答案：A。因为已经把 p 握在手里，只需让新节点指向 p.next，再让 p.next 指向新节点，改两条指针即可。O(n) 是“只知道第 k 个下标”时的定位成本，与已知节点指针是两个问题。就像调度员已经站在车厢旁，挂车厢只动两个挂钩。

Q2. 与单链表相比，双向链表最直接的新增能力是什么？

单选题 · easy

A.每个节点可以访问前驱节点← 正确答案
B.节点自动按值排序
C.不需要任何指针也能遍历
D.内存占用更小

答案：A。双向链表的每个节点多了一个 prev 指针，因此可以从任意节点向前走。B 是排序算法的职责，C 没有指针就不成链表，D 与事实相反——双链表比单链表更耗内存。

Q3. 用 cur 从 head 开始遍历循环链表，判断 cur 是否是尾结点的条件是什么？

单选题 · mid

A.cur.next == head← 正确答案
B.cur.next == null
C.cur.next == cur
D.cur.value == head.value

答案：A。循环链表的尾结点不再指向空，而是指向 head，所以 cur.next == head 是识别尾结点的标志。C 只在链表中只剩一个节点时成立。就像环线列车的最后一节车厢通常挂回第一节，而不是指向空气。

Q4. 删除双向链表中已知节点 p（不考虑释放节点），至少需要修改几条 next/prev 指针？

单选题 · mid

A.1 条
B.2 条← 正确答案
C.3 条
D.4 条

答案：B。需要让 p 的前驱的 next 指向 p 的后继，同时让 p 的后继的 prev 指向 p 的前驱，共两条指针赋值。不需要修改 p 自己的指针，因为它即将被释放。比喻：拆掉一节车厢，只需要把前后两节车厢的挂钩重新对接。

Q5. 与数组相比，链表更适合哪些场景？

多选题 · mid

A.频繁在中间插入和删除← 正确答案
B.需要频繁按下标随机读取
C.数据规模动态变化且难以预估← 正确答案
D.对 CPU 缓存命中率要求极高

答案：AC。链表在已知位置增删是 O(1)，且节点按需创建，适合规模未知的动态数据。数组按下标随机访问 O(1)，且连续内存更利于缓存预取，因此 B、D 是数组的优势场景。就像调度员在列车中途挂卸车厢很顺手，但按门牌号直达仓库更不是他的强项。

Q6. 哨兵头节点（dummy head）的主要作用是什么？

单选题 · easy

A.统一空链表和删除头节点的边界逻辑← 正确答案
B.让查找时间复杂度变成 O(1)
C.让每个节点都存储值
D.完全替代尾指针

答案：A。哨兵节点不存业务数据，只充当固定的“虚拟前驱”，使空表和普通表都有统一结构，删除头节点时无需特判。它并不改变查找复杂度，也不能替代 tail 完成尾部 O(1) 插入。相当于月台上放一节空引导车厢，让调度员永远不用面对“没有车厢”的尴尬。

Q7. 用循环链表模拟约瑟夫问题：n 个人围成一圈，每次数到 k 的人出列，时间复杂度是多少？

单选题 · hard

A.O(n)
B.O(k)
C.O(nk)← 正确答案
D.O(n log n)

答案：C。每淘汰一个人，都要沿 next 移动 k 步，总共要淘汰 n-1 个人，所以总步数约为 (n-1)k，即 O(nk)。数学递推法可以做到 O(n)，但那是另一套算法。就像每转一圈数 k 节车厢，一共要清空 n-1 节，绕圈总距离自然与 n 和 k 都成正比。

Q8. 给定循环链表中的某个节点 p，且无法访问头节点，要在 O(1) 时间“删除 p 本身”，可行做法是什么？

多选题 · extreme

A.将 p.next 的值复制到 p.value← 正确答案
B.让 p.next = p.next.next← 正确答案
C.若 p.next == p，则释放 p 并把外部指针置空
D.必须从头遍历找到 p 的前驱

答案：AB。经典“复制后驱法”：把后继节点的值复制到 p，再让 p 跳过这个后继节点，相当于借尸还魂。C 无法做到，因为外部没有引用的情况下你无法把别人的指针置空；D 会破坏 O(1) 要求。就像最后一节车厢的车牌可以换成前一节的，然后拆掉前一节，达到“原地换芯”。

Q9. 关于数组和链表的 CPU 缓存局部性，下列说法正确的是？

单选题 · mid

A.数组遍历更利于 CPU 缓存预取← 正确答案
B.链表节点可能分散在内存各处，遍历容易缓存未命中
C.链表遍历速度一定比数组快
D.使用内存池连续分配节点不能改善链表表现

答案：A。数组元素连续存放，CPU 会把一块内存一次性载入缓存；链表节点靠指针串联，往往分散分配，每次跳转都可能未命中。C 过于绝对，D 与事实相反——内存池能让节点尽量相邻，有效改善局部性。就像沿着一排货架走总比在仓库里到处跑快。

Q10. 双向链表维护 tail 尾指针，最主要的好处是什么？

单选题 · mid

A.在链表尾部插入时无需从头遍历，时间复杂度为 O(1)← 正确答案
B.自动让所有节点按值排序
C.让链表自动变成循环链表
D.减少每个节点存储的指针数量

答案：A。没有 tail 时，尾部插入要先遍历整个链表找到尾结点，是 O(n)；有 tail 就能直接站在尾结点旁边挂新节点，变成 O(1)。B、C 与尾指针无关，D 恰恰相反——双链表每个节点有两个指针，并不会减少。就像调度室掌握了列车最后一节的位置，挂新车厢自然省时。