第十一单元：链表操作 · 节点、遍历与链接维护

封神冰川的深处，散落着一串串"手拉手"的伙伴：拿钥匙的农民一个牵着一个、待命的大炮一门连着一门、活着的宝石一颗接着一颗、守护要塞的机器人一台指向下一台。它们不像数组那样整整齐齐地挤在一起排排坐，而是每个元素都藏着一根"指向下一个"的隐形丝线——这就是链表（linked list）。这一单元由四个关卡组成，你将系统掌握计算机科学中另一个基础而优雅的数据结构：链表（linked list），以及它"逐个链接、随需伸缩"的独特智慧。

11.1.1 什么是链表（What Is a Linked List）

11.1.1.1 一串"手拉手"的独立对象 A chain of separate objects linked one to the next

链表是一种线性数据结构，其中每个元素都是一个单独的对象（节点）。每个节点由两部分组成：它自己承载的数据，以及一个指向下一个节点的引用（next）。最后一个节点的 next 指向"空"（None / null），标志着链表的终点。整条链表的入口叫作头（head）——注意，head 并不是一个额外的单独元素，而只是"对第一个节点的引用"。

11.1.2 节点与 next 属性（Nodes and the next Property）

11.1.2.1 数据 + 指针 = 一个节点 Data plus a pointer makes one node

在 扣哒世界 的关卡里，每个"节点"就是一个游戏单位（农民、大炮、宝石、机器人）。它承载的数据是这个单位本身的属性（如 type、health、pos），而 next 属性则存着"下一个单位"的引用。用第一个农民的 next 就能拿到第二个农民，用第二个农民的 next 就能拿到第三个，以此类推。

# "链接的钥匙"关卡：用 next 逐个访问节点
head = hero.findNearest(hero.findFriends())   # 头 = 对第一个节点的引用
secondPeasant = head.next          # 第二个 = 第一个的 next
thirdPeasant = secondPeasant.next   # 第三个 = 第二个的 next

11.1.3 链表 vs 数组（Linked List vs Array）

11.1.3.1 各有所长的两种线性结构 Two linear structures, each with strengths

链表最大的特点是大小不固定，可以随需要增长或缩小；在头尾插入/删除元素又快又省事。但它有个明显缺点：不支持直接（随机）访问。想访问第 n 个元素，必须从头开始、顺着 next 一步步走 n 次才能到达——这正是下面"计数链接"关卡要解决的问题。数组则相反：随机访问飞快（直接用下标），但中间插入/删除较麻烦。

11.2.1 从头到尾走一遍（Walk from Head to Tail）

11.2.1.1 用一个"游标"沿 next 前进 Use a cursor that moves along next

遍历（traversal）就是从头节点出发，顺着每个节点的 next 引用一路访问到链表末尾。核心套路是：先把游标 current 指向头节点，处理完当前节点后，用 current = current.next 让游标"跳"到下一个节点，如此循环。这就是"链接的钥匙"关卡里指挥每个农民开门的基本框架。

# 遍历链表的标准套路
current = linkedList          # 游标指向头节点
while current:              # 只要 current 不是 None 就继续
    # … 在这里处理 current 节点 …
    current = current.next   # 关键一步：游标前进到下一个节点

11.2.2 null 判断结束（Stopping at null）

11.2.2.1 没有 next 就是到头了 No next means the end of the list

怎么知道遍历该停了？答案是：当某个节点的 next 为空（None）时，说明它是最后一个节点，链表到此结束。在 Python 里，可以直接用 while current: ——当 current 变成 None 时循环条件自动为假、循环终止；也可以在循环体里写 if not current.next: break 提前跳出。

# "链接的钥匙"里的结束判断
currentPeasant = currentPeasant.next
if not currentPeasant:   # 没有下一个了 → 链表结束
    break

11.3.1 循环 next 定位（Loop next to Locate）

11.3.1.1 想到第 n 个，就走 n 步 To reach index n, follow next n times

链表不能像数组那样用 list[n] 直接取第 n 个元素。要访问索引为 index 的节点，必须从头开始循环 next 走 index 次。这正是"计数链接"关卡里 elementByIndex 函数的核心：用一个 for i in range(index) 循环，每轮让游标 current = current.next,走完就到达目标节点。

# "计数链接"：按索引查找元素
def elementByIndex(linkedList, index):
    current = linkedList
    for i in range(index):       # 从 0 到 index（不含）
        current = current.next   # 每次前进一步
        if not current:          # 越界保护：中途到头就停
            break
    return current                # 第 index 个节点（或 None）

11.3.2 越界与判空（Out-of-Range and null Checks）

11.3.2.1 索引超出链表长度怎么办 What if the index exceeds the list length

如果传入的 index 比链表实际长度还大，游标走着走着就会碰到 None。此时若继续 None.next 就会报错。所以在循环内每次前进后都要判空：if not current: break,一旦游标为空立即跳出，函数最终返回 None 表示"没有这个索引的元素"。这是链表操作里必不可少的边界防护。

11.4.1 头部插入（Insert at the Head）

11.4.1.1 让新节点指向旧头，成为新头 Point the new node at the old head to make it the new head

在链表头部插入一个新节点很简单：让新节点的 next 指向当前的头节点，然后把"头"这个引用改成新节点。两步就完成，不需要移动任何其他元素——这正是链表相对数组的优势之一。

# 头部插入：新节点变成新的头
headList = hero.findNearestItem()
gem3.next = headList   # 新节点指向旧头
headList = gem3        # 现在 gem3 是新的头

11.4.2 尾部追加（Append at the Tail）

11.4.2.1 让当前尾节点指向新节点 Point the current tail at the new node

在尾部追加，就是把当前最后一个节点的 next(原本是 None) 改为指向新节点。在"宝石生宝石"关卡里，你要用 next 属性把散落的自由宝石逐个链接到基础宝石的前后，最终拼成一条能开门的完整链表。

# "宝石生宝石"：用 next 拼接链表
freeGems[0].next = baseGem       # 在基础宝石之前追加
freeGems[1].next = freeGems[0]  # 再往首部前面接一个
baseGem.next = freeGems[2]      # 在最后追加更多宝石

11.5.1 setNext 方法（Using setNext）

11.5.1.1 有些链表不让直接改 next Some lists forbid assigning next directly

在"无线电"关卡里有一条重要规则：不能直接给 next 属性赋值，必须用 setNext(unit) 方法。很多真实的链表实现会把 next 封装起来，只允许通过方法修改——这样能在设置链接时附带做校验或其他处理。所以在这一关，凡是要改链接的地方，都写成 node.setNext(其他节点),而不是 node.next = 其他节点。

11.5.2 记录 prev 前驱（Tracking the Previous Node）

11.5.2.1 替换中间节点为何要记住前一个 Why replacing a middle node needs the previous one

在头尾增删很轻松，但替换/删除链表中间的节点就麻烦些。因为要让"坏节点的前一个节点"改为指向"替换节点",可我们遍历时手上只有 current,没法回头找前驱。解决办法是：遍历时用一个额外变量 prev 始终记住"上一个访问过的节点"。找到坏节点后,就用 prev.setNext(replacement) 接上替换节点,再让替换节点的 next 指向坏节点原来的后继,链条就无缝修复了。

# 替换中间节点的通用套路（含前驱 prev）
current = linkedList
prev = None
while current:
    if current == broken:          # 找到要替换的节点
        if prev:
            prev.setNext(replacement)            # 前驱接上替换节点
            replacement.setNext(current.next)   # 替换节点接回原后继
        break
    prev = current               # 记住当前，作为下一轮的前驱
    current = current.next        # 游标前进

11.6.1 null 检查（Null Checks）

11.6.1.1 访问节点前先确认它存在 Make sure a node exists before using it

链表操作最常见的崩溃原因就是"对 None 取属性"——比如空链表却去读 head.next,或遍历越过尾部还继续 current.next。防护方法很统一：凡是要访问节点或它的 next 之前,先检查这个节点不是 None。用 while current:、if not current: break、if prev: 这些判断把边界情况稳稳兜住。

# "无线电"里带血量判断的遍历（同时做 null 检查）
def diagnoseList(linkedList):
    current = linkedList
    # current 为真（非 None）且血量健康时，继续往后走
    while current and current.health > 0:
        current = current.next
    return current   # 返回第一个坏掉的（或 None 表示全健康）

这一节聚焦每一关的策略、思路与算法设计,只展示用于说明的关键片段,完整通关程序请你自己动手完成。

第 24 关 · 链接的钥匙

🔑 链接的钥匙 —— 遍历链表逐个开门

图2：链接的钥匙——拿钥匙的农民组成链表，从头节点沿 next 逐个指挥去开对应的门,实践最基本的链表遍历

策略:顺着链表,让每个农民开对应的门

拿钥匙的农民被组织成一条链表,最近的农民是头(第一个),他们开门的顺序与门的顺序一一对应。策略很直接:从头节点开始遍历链表,每访问到一个农民,就命令他去开当前 doorIndex 对应的那扇门,然后 doorIndex 加一、游标前进到下一个农民,直到链表走完。

思路拆解:遍历 + 同步递增门索引

用 currentPeasant 作游标从头开始;循环体里先算出这扇门的坐标 pos,命令农民 dropItem 到那里;再用 currentPeasant = currentPeasant.next 前进;若 next 为空则 break;最后 doorIndex += 1。关键在于让"农民的顺序"与"门的索引"始终同步。

# 关键片段:遍历农民链表逐个开门
currentPeasant = peasantLinkedList   # 游标 = 头节点
while True:
    pos = {"x": 20 + doorIndex * doorDistance, "y": 34}
    hero.command(currentPeasant, "dropItem", pos)
    currentPeasant = currentPeasant.next   # 前进到下一个农民
    if not currentPeasant:   # 没有下一个 → 链表结束
        break
    doorIndex += 1          # 门索引同步递增

head 只是引用:切记 peasantLinkedList(头)不是一个额外的单位,而就是"对第一个农民的引用"。head.next 是第二个,head.next.next 是第三个……理解了这一点,后面用循环代替一长串 .next.next.next 就顺理成章。

第 25 关 · 计数链接

🎯 计数链接 —— 按索引查找合适的大炮

图3：计数链接——大炮连成链表,第 n 门发 n+1 发炮弹;按敌人数量算出索引,循环 next 精确定位那门炮

策略:算出需要的索引,再循环 next 找到那门炮

五门大炮连成链表,索引 0 的发 1 发、索引 1 的发 2 发……即索引 i 的发 i+1 发。当出现 k 个敌人时,要用能发 k 发的那门炮,也就是索引 k-1 的大炮。策略:实现一个 elementByIndex(linkedList, index) 函数,从头循环 next 走 index 步找到目标节点,再把它说出来即可。

思路拆解:for 循环走 index 步 + 越界判空

函数里游标 current 从头开始,用 for i in range(index) 让它前进 index 次;每次前进后判空 if not current: break 防越界;循环结束返回 current。主循环里用 elementByIndex(cannonList, len(enemies)-1) 定位合适的炮。

# 关键片段:按索引查找 + 主循环调用
def elementByIndex(linkedList, index):
    current = linkedList
    for i in range(index):
        current = current.next
        if not current:
            break
    return current

# 主循环:敌人多于 8 时,找到炮弹够用的那门炮
if len(enemies) > 0:
    hero.say(elementByIndex(cannonList, len(enemies) - 1))

索引与"发数"差 1:最容易错的就是索引换算——想发 k 发,要的是索引 k-1 的炮,而不是索引 k。因为索引从 0 开始:索引 0 发 1 发。把这个"减一"关系想清楚,才能精准打击。

链表随机访问的代价:这一关直观展示了链表的短板——想拿第 n 门炮,不能一步到位,得从头走 n 步。这就是为什么"频繁按位置访问"的场景更适合用数组。链表擅长的是顺序遍历和两端增删。

第 26 关 · 宝石生宝石

💎 宝石生宝石 —— 用 next 亲手拼接链表

图4：宝石生宝石——用 next 属性把自由宝石链接到基础宝石前后,拼出一条完整链表来开门

策略:在头部和尾部插入,把宝石串成链

活着的宝石能帮你开门。有一颗基础宝石(root-gem),还有几颗散落的自由宝石。目标是用 next 属性把它们链成一条表,并让基础宝石处于结果链表的索引 2(第三个)位置。这意味着:基础宝石前面要接两个宝石(头部插入),后面再接更多(尾部追加)。

思路拆解:头部两次插入 + 尾部追加

要让基础宝石排在索引 2,就得在它前面放两颗:先 freeGems[0].next = baseGem(freeGems[0] 排在基础宝石前),再 freeGems[1].next = freeGems[0](freeGems[1] 成为更前的头)。这样顺序是 freeGems[1] → freeGems[0] → baseGem,基础宝石正好在索引 2。最后 baseGem.next = freeGems[2] 在尾部续上更多宝石。

# 关键片段:用 next 拼接宝石链表
baseGem = hero.findByType("root-gem")[0]
freeGems = hero.findByType("gem")

freeGems[0].next = baseGem        # 在基础宝石之前追加
freeGems[1].next = freeGems[0]   # 再在首部前面接一个(新头)
baseGem.next = freeGems[2]       # 在最后追加更多宝石

gem1● → gem0● → base(索引2)● → gem2●

数清索引再动手:本关的关键是让基础宝石落在索引 2。链表索引从 0 数起,所以它前面必须恰好有两个节点。动手拼之前,先在纸上画出目标顺序,再逐条设置 next,就不会接错。

头尾插入是链表的强项:这一关正是链表"随需扩展"优势的体现——无论在头部还是尾部加宝石,都只是改一根 next 引用,轻松又高效。这也是链表被广泛用于需要动态增删的数据场景的原因。

第 27 关 · 无线电

📡 无线电 —— 用 setNext 替换损坏的中间节点

图5：无线电——机器人连成链表逐个传递等离子;诊断出损坏节点,用备份机器人和 setNext 修复链条

策略:先诊断坏节点,再用 setNext 替换修复

机器人连成链表,首个被等离子击中后会沿链条依次射击,next 为空的最后一个会转而攻击最近的敌人。其中一台机器人快坏了,你要用更强的备份机器人替换它来修复链表。本关分两步:① 诊断(diagnose)——遍历链表找出那个损坏的节点;② 替换(replace)——用 setNext 把备份机器人接进链条。重点:本关不能直接给 next 赋值,必须用 setNext(unit) 方法。

思路拆解一:遍历诊断损坏节点

diagnoseList 从头遍历,用 while current and current.health > 0 一路前进——健康的机器人血量 > 0,一旦碰到血量为 0 的坏机器人,循环停下,此时 current 就是坏节点;若全都健康则最终返回 None。条件里把 current 判空放在 and 左边,巧妙利用短路避免空指针错误。

# 关键片段一:遍历诊断,返回坏节点(或 None)
def diagnoseList(linkedList):
    current = linkedList
    while current and current.health > 0:
        current = current.next
    return current

思路拆解二:记录前驱,用 setNext 双向接线

replaceMissingLink 遍历时用 prev 记住前驱。找到坏节点后:先 prev.setNext(replacement) 让前驱接上备份机器人,再 replacement.setNext(current.next) 让备份机器人接回坏节点原来的后继。两根链接都接好,坏节点就被无缝绕过。别忘了 if prev: 的判空保护。

# 关键片段二:用 setNext 替换中间节点
def replaceMissingLink(linkedList, broken, replacement):
    current = linkedList
    prev = None
    while current:
        if current == broken:
            if prev:
                prev.setNext(replacement)              # 前驱→备份
                replacement.setNext(current.next)   # 备份→原后继
            break
        prev = current
        current = current.next

必须用 setNext,不能直接赋值:这是本关最容易踩的坑——机器人节点的 next 被封装了,写 prev.next = replacement 无效,必须写 prev.setNext(replacement)。同理接后继也要用 replacement.setNext(current.next)。看清关卡规则,用对接口。

备份机器人的筛选:关卡还要用 findBackupRobots 筛出血量足够高(如 > 5000)的机器人作为可靠替换。这提醒我们:替换节点前先确保"替换品"本身是合格的——遍历筛选 + 链表替换,两个技能在这一关组合运用。

11.8.1 新手最容易踩的坑（Pitfalls for Beginners）

11.8.1.1 链表操作的典型问题 Typical issues with linked list operations

图6：忘记游标前进、不做 null 检查、替换只接一半、该用 setNext 却直接赋值,是本单元最常见的失误