Lab 8：链表（Linked Lists）ok 7 项通过
用一个只有 first 和 rest 两个属性的类，把「序列」这个概念从零重建一遍：递归地构造、递归地拆解、就地修改，以及当 rest 指回自己时会发生什么。
0. 这份作业在练什么
前面几周你一直在用 Python 内置的 list。它很好用，但它是一个「黑盒」：你不知道 lst[3] 为什么那么快，也不知道 lst.insert(0, x) 为什么那么慢。这次作业要做的事情是——把序列这个抽象自己造一遍。造出来的东西叫链表（linked list），在这门课里由 Link 类实现。
链表的定义只有一句话，但这句话是递归的，请把它背下来：
一个链表要么是 Link.empty（空链表），要么是一个 Link 实例，它有两个实例属性：
first：这个链表的第一个元素（可以是任何值）；rest：剩下的部分，而剩下的部分本身又是一个链表——要么是另一个Link实例，要么是Link.empty。
rest 永远不应该是 None，也不应该是一个普通的数或字符串。
这个定义为什么重要？因为它决定了这次五道题的全部解法形状。当一个数据结构的定义是「一个 X 由一个头部 + 一个更小的 X 组成」时，处理它的函数几乎必然长成这样：
def f(s):
if s is Link.empty:
# base case：最小的那个 X，直接给答案
...
else:
# 用 s.first 做点事，然后把 f 递归地用在 s.rest 上
... s.first ... f(s.rest) ...
这就是 CS 61A 反复强调的那句话：数据的形状决定代码的形状。你在做「树」那一周会再见到它，在 Scheme 那几周会天天见到它。
先把 Link 类读懂
这是 labs/lab08/lab08.py 里真实的 Link 类实现（作业不要求你写它，但每道题都建立在它之上）：
class Link:
"""A linked list.
>>> s = Link(1)
>>> s.first
1
>>> s.rest is Link.empty
True
>>> s = Link(2, Link(3, Link(4)))
>>> s.first = 5
>>> s.rest.first = 6
>>> s.rest.rest = Link.empty
>>> s # Displays the contents of repr(s)
Link(5, Link(6))
>>> s.rest = Link(7, Link(Link(8, Link(9))))
>>> s
Link(5, Link(7, Link(Link(8, Link(9)))))
>>> print(s) # Prints str(s)
(5 7 (8 9))
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest is not Link.empty:
rest_repr = ', ' + repr(self.rest)
else:
rest_repr = ''
return 'Link(' + repr(self.first) + rest_repr + ')'
def __str__(self):
string = '('
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + ')'
逐条拆开看，这里面有四个设计决定，每一个都会在后面的题目里咬你一口：
empty = () 是类属性（class attribute），不是实例属性。也就是说全世界只有一个空链表对象，它就是那个空元组。因为只有一个，所以判断「是不是空」可以也应该用 is：s is Link.empty。用 == () 也能得到 True，但那样你就依赖了「empty 恰好是元组」这个实现细节，破坏了抽象屏障（abstraction barrier）。def __init__(self, first, rest=empty) 中的默认参数 rest=empty。注意这里写的是裸的 empty 而不是 Link.empty——因为这行代码是在类体内部执行的，此刻 Link 这个名字还没绑定到全局，但 empty 已经在类体的局部作用域里了。这个默认值让 Link(4) 直接构造出长度为 1 的链表。assert rest is Link.empty or isinstance(rest, Link)。这是一道主动设置的护栏：它保证任何一个 Link 实例的 rest 一定是合法链表。你写 Link(1000, 2000) 会当场 AssertionError，而不是等到某个函数里 2000.rest 才报 AttributeError。让错误尽早暴露是好的库设计。__repr__ 递归、__str__ 迭代。repr 给出的是「怎么把它造出来」的表达式 Link(5, Link(6))；str 给出的是 Scheme 风格的紧凑写法 (5 6)。交互式解释器直接回显一个值时用 repr，print() 用 str。这个区别在下面 Q1 里会被直接考。Python 的 list 是一整块连续内存，所以 lst[i] 是 $\Theta(1)$，但在开头插入一个元素要把后面所有元素往后挪，是 $\Theta(n)$。链表反过来：每个节点独立分配、靠 rest 串起来，所以在已知位置插入一个新节点只需要改两个指针，是 $\Theta(1)$；但要取第 i 个元素必须从头走 i 步，是 $\Theta(i)$。没有免费的午餐，只有取舍。
| 操作 | Python list | Link 链表 |
|---|---|---|
取第 i 个元素 | $\Theta(1)$ | $\Theta(i)$，得一路 .rest 走过去 |
| 在开头插入 | $\Theta(n)$，后面全要挪 | $\Theta(1)$，Link(x, s) 就完了 |
| 在已到达的节点后插入 | $\Theta(n)$ | $\Theta(1)$，改 rest |
| 求长度 | $\Theta(1)$（长度被存着） | $\Theta(n)$，只能数 |
| 共享尾部（结构共享） | 做不到，切片必复制 | 天然支持，多个链表可共用同一段 rest |
- Q1 WWPD：确认你真的懂
first/rest、is Link.empty、构造器里的assert、以及repr与str的差别。 - Q2 without：递归构造一个新链表，同时不动原表——练「什么时候必须复制、什么时候可以共享」。
- Q3 duplicate_link：迭代就地修改链表——练指针改写，以及怎样避免把自己刚插进去的副本又复制一遍导致死循环。
- Q4 slice_link：带两个「窗口」参数的递归——练如何用参数的变化表示「我走到哪了」。
- Q5 has_cycle：环检测。先用 $\Theta(n)$ 空间的朴素法，再用 Floyd 快慢指针做到 $\Theta(1)$ 空间。这道题会逼你彻底分清
is（同一个对象）和==（值相等）。
做之前该掌握什么
类与实例属性（Lecture 12–13 的对象系统）、__init__ / __repr__ / __str__ 这三个特殊方法的触发时机、可变对象与别名（aliasing）、以及递归的基本套路（base case + 递归调用 + 用返回值拼答案）。如果「递归调用返回的东西要拿来干嘛」这一步还不熟，Q2 会很难受——那道题的关键正是「递归调用替我把后面全做完了，我只负责我这一个节点」。
本地评分结果
在本仓库的 labs/lab08/ 目录下运行 python3 ok --local，结果是 7 个测试用例全部通过，也就是 Q1 的三组 WWPD 加上 Q2–Q5（含选做的 has_cycle_constant）的全部函数测试。下面贴出的每一段作业代码都与该目录下的真实文件逐字一致。
1. WWPD：Linked Lists
题目要什么
这是一组「What Would Python Display?」（Python 会显示什么）概念题，通过 python3 ok -q link -u 交互作答。它不写代码，只考你对 Link 类语义的理解。规则：如果答案是 <function ...> 就填 Function；如果会报错就填 Error；如果什么都不显示就填 Nothing。
题目分三组，对应 labs/lab08/tests/link.py 里的三个 case。下面逐条讲为什么是那个输出。
第一组：构造与护栏
>>> link = Link(1000)
>>> link.first
1000
>>> link.rest is Link.empty
True
>>> link = Link(1000, 2000)
Error
>>> link = Link(1000, Link())
Error
link = Link(1000)：调用 Link.__init__(self, 1000)，rest 走默认值 Link.empty。assert 检查 rest is Link.empty —— 成立，通过。于是 self.first = 1000，self.rest = ()。赋值语句本身不显示任何东西。link.first 求值得到 1000，交互式解释器回显 repr(1000)，即 1000。link.rest is Link.empty：link.rest 就是构造时存进去的那个 Link.empty 对象本身，is 比较的是身份（identity）——是不是同一个对象。是，所以 True。Link(1000, 2000)：assert 2000 is Link.empty or isinstance(2000, Link)。2000 既不是那个空元组，也不是 Link 实例，断言为假，抛出 AssertionError。ok 里填 Error。Link(1000, Link())：这次错在内层。Link() 一个参数都不给，但 __init__ 的 first 是必填的位置参数（只有 rest 有默认值），于是 Python 在真正进入函数体之前就抛 TypeError: __init__() missing 1 required positional argument: 'first'。注意求值顺序：算子数（operand）先于外层调用求值，所以外层的 Link(1000, ...) 根本没机会执行。ok 里同样填 Error。官方题面在这两行分别标了 AssertionError 和 TypeError，但 tests/link.py 里期望的答案都是 Error。你在 ok 里填 Error 即可；不过能说出是哪一种错误、错在哪一步，才说明你真的读懂了 __init__。
第二组：可变性、别名与环
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
1
>>> link.rest.first
2
>>> link.rest.rest.rest is Link.empty
True
>>> link.first = 9001
>>> link.first
9001
>>> link.rest = link.rest.rest
>>> link.rest.first
3
>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest is Link.empty
False
>>> link.rest.rest.rest.rest.first
1
>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first
1
>>> link2.rest.first
2
把 Link(1, Link(2, Link(3))) 画成盒子指针图（box-and-pointer diagram）：
link ──▶ ┌───────┬───────┐ ┌───────┬───────┐ ┌───────┬───────┐
│ first │ rest │──▶│ first │ rest │──▶│ first │ rest │──▶ Link.empty
│ 1 │ │ │ 2 │ │ │ 3 │ │
└───────┴───────┘ └───────┴───────┘ └───────┴───────┘
节点 A 节点 B 节点 C
link.first → 节点 A 的 first → 1。link.rest.first → 先取 A 的 rest（节点 B），再取 B 的 first → 2。属性访问从左到右一步步走，没有魔法。link.rest.rest.rest → A→B→C→C 的 rest，也就是 Link.empty。is Link.empty 得 True。这就是「链表末端」的标准判定方式。link.first = 9001：这是属性赋值，它修改的是节点 A 这个对象内部的 first 槽位。赋值语句不显示东西。随后 link.first 显示 9001。链表是可变的，这是它和 Scheme 里不可变 pair 的重要区别，也是 Q3 的全部基础。link.rest = link.rest.rest：右边先算——link.rest 是 B，B.rest 是 C，所以右边求值为节点 C。然后把 A 的 rest 改成指向 C。图变成 A(9001) → C(3) → empty，节点 B 被绕过了（没人再指向它，会被垃圾回收）。所以 link.rest.first 是 3。接下来这三行是整组题最值钱的部分：
>>> link = Link(1)
>>> link.rest = link
link.rest = link 让节点自己指向自己。注意 assert 拦不住这个：断言只在 __init__ 里跑一次，而这是事后的属性赋值；而且 link 确实是一个合法的 Link 实例，即使它拦了也拦不下来。
┌─────────────┐
│ │
▼ │
link ──▶ ┌───────┬──────┴┐
│ first │ rest │ rest 指回自己
│ 1 │ ●───┼───┐
└───────┴───────┘ │
▲───────────┘
link.rest.rest is Link.empty：link.rest 是它自己，link.rest.rest 还是它自己，是一个 Link 实例，不是空元组。所以 False。link.rest.rest.rest.rest.first：无论你写多少个 .rest，都还在同一个节点上打转，最后 .first 取到 1。这就是「环形链表」。它无限长——如果你对它调用 print()，__str__ 里的 while self.rest is not Link.empty 永远不会停，程序会挂住直到内存耗尽。Q5 就是专门来检测这种情况的。link2 = Link(1, link) 并没有复制 link，只是让新节点的 rest 指向已存在的 link。所以 link2.first 是 1，link2.rest.first 是 link.first 即 2。这种「新表和旧表共享同一条尾巴」的现象叫结构共享，Q2 会主动利用它。第三组：repr 与 str
>>> link = Link(5, Link(6, Link(7)))
>>> link # Look at the __repr__ method of Link
Link(5, Link(6, Link(7)))
>>> print(link) # Look at the __str__ method of Link
(5 6 7)
在交互式解释器里单独求值一个表达式，显示的是 repr(值)；而 print(x) 显示的是 str(x)。两个方法的实现风格恰好相反，值得对照：
__repr__ | __str__ | |
|---|---|---|
| 触发时机 | 解释器回显、放进容器里显示 | print()、str()、f-string |
| 实现方式 | 递归：repr(self.rest) | 迭代：while 循环挪 self |
| 输出风格 | 能重新求值造出这个对象 | Scheme 风格 (5 6 7)，给人看 |
| 对空链表 | 不会被调用（Link.empty 是元组，显示 ()） | 同左 |
推演 repr(Link(5, Link(6, Link(7))))：最内层 Link(7) 的 rest is Link.empty，所以 rest_repr = ''，返回 'Link(7)'；中层拿到它，返回 'Link(' + '6' + ', Link(7)' + ')' 即 'Link(6, Link(7))'；最外层同理得到 'Link(5, Link(6, Link(7)))'。
推演 str：循环条件是 self.rest is not Link.empty，所以循环体只处理「不是最后一个」的节点，把 '5 '、'6 ' 依次拼进去，然后 self 挪到下一个；当 self 是 Link(7) 时循环退出，最后 return string + str(self.first) + ')' 补上 '7)'。这样最后一个元素后面就不会多一个空格，得到 (5 6 7)。
误区一：以为 Link(1000, 2000) 会静默接受。 很多人第一反应是「rest 反正就是存个值，存 2000 有什么问题」。问题在于链表的不变量（invariant）被破坏了：一旦 rest 不是链表，所有递归函数在 s.rest.first 处都会炸成 AttributeError: 'int' object has no attribute 'first'，而且报错位置离真正的错误现场很远。assert 的价值就是把爆炸点搬到犯错的那一行。
误区二：把 link.rest = link.rest.rest 读成「删掉第二个元素的值」。 它删的不是值，是指针。节点 B 这个对象还好端端地存在于内存里，只是没人指着它了。区分「对象」和「指向对象的名字/属性」是这门课的核心功。
误区三：用 == 判断空。 s == Link.empty 在这份实现下确实能工作（因为 empty 是元组，而 Link 没定义 __eq__），但它依赖了实现细节。官方 checkoff 问题明确说了：应该用 s is Link.empty，因为 Link.empty 是唯一的类属性，is 是最可靠的判定。
验证
运行 python3 ok -q link -u 逐条作答，三个 case 全部通过；答案已在 tests/link.py 中以明文形式解锁（'locked': False），与上面推演的结果一致。
2. Without One without
题目要什么
写一个函数 without(s, i)，接收一个链表 s 和一个非负整数 i，返回一个新的链表，内容和 s 一样，但少了下标为 i 的那个元素（s.first 算下标 0）。硬性要求：原链表 s 不能被改动。
>>> s = Link(3, Link(5, Link(7, Link(9))))
>>> without(s, 0)
Link(5, Link(7, Link(9)))
>>> without(s, 2)
Link(3, Link(5, Link(9)))
>>> without(s, 4) # There is no index 4, so all of s is retained.
Link(3, Link(5, Link(7, Link(9))))
把 docstring 翻译成人话，并把边界情况点清楚：
| 情况 | 该返回什么 | 为什么 |
|---|---|---|
i == 0 | 去掉头，返回后面全部 | 要删的就是当前这个头 |
i 大于等于长度 | 原样返回全部元素 | 第三个 doctest 明确规定：没有这个下标就什么都不删 |
s 是 Link.empty | Link.empty | 空表里没有任何元素可删，也没什么可保留 |
调用后再看 s | 必须和调用前一模一样 | 题目明说 “The original linked list s should not be changed” |
特别注意第三个 doctest 的存在感：without(s, 4) 在一个长度为 4 的表上被调用，下标 4 越界。它没有报错、没有返回 None，而是把整个表原样交回来。这条 doctest 其实是在告诉你 base case 该怎么写——很多题面里那种「看似多余的例子」，实际上是在替你指定边界行为。
怎么想到的
先说一条走不通、或者说很痛苦的路，因为大多数人第一反应就是它。
弯路：迭代 + 手动接线。 思路是「用一个 while 循环走到第 i-1 个节点，然后把它的 rest 改成 rest.rest」。这个想法在「删除节点」这件事上是对的，但它修改了原表，直接违反题目要求。那就退一步：先把整个表复制一份，再在副本上做这件事。可是「复制一个链表」本身就得写一个循环，而且复制时你需要维护一个「尾指针」来往后接新节点，还要单独处理「新表还是空的、没有尾指针」这个第一步——代码会膨胀到十几行，边界情况一堆。题面给的 Hint 也直说了：“Using recursive approach might be easier than the iterative approach.”
转向：把问题写成它自己的小一号版本。 关键提问是：「without(s, i) 的答案，和 without(s.rest, i-1) 的答案之间是什么关系？」
盯着例子想。设 s = Link(3, Link(5, Link(7, Link(9))))，要算 without(s, 2)：
- 下标 2 不是 0，说明当前这个元素 3 要留下来。
- 剩下要处理的是
Link(5, Link(7, Link(9)))，而在这个更短的表里，原来的「下标 2」现在变成了「下标 1」。 - 所以答案 =
3接在without(s.rest, 1)的结果前面。
这就是递归关系。三种情况一一对应三个分支：
i == 0：当前元素正是要删的那个。删掉它以后，剩下的部分就是 s.rest——它已经完全正确了，直接返回，不需要任何加工。s is Link.empty：走到头都没等到 i 归零，说明下标越界。返回 Link.empty。注意这个分支必须排在前面，否则 i > 0 分支里的 s.first 会在空表上抛 AttributeError。i > 0 且表非空）：保留当前元素，把它装进一个全新的 Link，尾巴接上 without(s.rest, i - 1)。这里有一个非常值得单独拎出来讲的细节，它是这道题真正的考点：
i == 0 分支里直接 return s.rest——返回的是原表里那一段，不是副本。这不算「改动原表」吗？不算。「不改动」指的是不能修改任何已存在节点的 first 或 rest 属性。我们只是让新表和旧表共用一条尾巴，没有写入任何东西，两个表都还是完整正确的。
反过来，i > 0 分支里就必须新建：因为这个节点的 rest 在新表里要指向「删过元素的后半段」，而在原表里必须继续指向原来的后半段。同一个节点不可能同时有两个不同的 rest，所以只能造一个新的。
结论：只复制「rest 需要改变」的那部分前缀，改变点之后的整条尾巴原样共享。 这是函数式数据结构（persistent data structure）的标准手法，也是链表相对数组的一大优势——数组切片必须整块复制，链表可以共享。
代码
def without(s: Link, i: int) -> Link:
"""Return a new linked list like s but without the element at index i.
>>> s = Link(3, Link(5, Link(7, Link(9))))
>>> without(s, 0)
Link(5, Link(7, Link(9)))
>>> without(s, 2)
Link(3, Link(5, Link(9)))
>>> without(s, 4) # There is no index 4, so all of s is retained.
Link(3, Link(5, Link(7, Link(9))))
"""
if s is Link.empty:
# Ran off the end of s, so index i never existed. Nothing left to keep.
return Link.empty
elif i == 0:
# Drop this element. Everything after it is already correct, so we can
# reuse s.rest directly without copying it.
return s.rest
else:
# Keep this element, but in a brand new Link so that s is not mutated.
return Link(s.first, without(s.rest, i - 1))
逐行说明为什么是这样而不是别样：
if s is Link.empty: —— 用 is 不用 ==，理由见第 0 节。这个判断放在最前面是有讲究的：如果把 elif i == 0 提到前面，遇到 without(Link.empty, 0) 会返回 ().rest，元组没有 rest 属性，直接 AttributeError: 'tuple' object has no attribute 'rest'。永远先检查「还有没有东西」，再检查「这个东西怎么样」。return Link.empty —— 返回的是那个唯一的空链表对象，而不是 None、不是 () 字面量、也不是 Link(None)。返回 None 会让上一层的 Link(s.first, None) 触发 assert 失败。elif i == 0: return s.rest —— 一行完事。很多人在这里会忍不住写成 return without(s.rest, -1) 之类，想「统一处理」。不必要，而且 i 变负数后 i == 0 永远不成立，反而会把后面的元素全复制一遍（虽然结果碰巧还是对的，但白白多做了 $\Theta(n)$ 的复制）。当答案已经现成时，直接返回。return Link(s.first, without(s.rest, i - 1)) —— 这一行同时做了三件事：(a) 用 Link(...) 新建节点，保证不碰原表；(b) s.first 原样搬过去，元素本身不复制（如果元素是可变对象，新旧表共享同一个元素对象，这是符合预期的浅拷贝语义）；(c) i - 1 表示「往后走了一步，目标下标也要跟着往前挪一格」。这个「参数随位置同步变化」的技巧在 Q4 里会被用两次。return。这不是巧合——纯递归构造天然不需要中间变量，因为「递归调用的返回值」就充当了那个变量。如果你发现自己在递归函数里写了一堆临时变量和循环，通常说明还没找到正确的递归关系。验证
手动追踪 without(s, 2)，其中 s = Link(3, Link(5, Link(7, Link(9))))。为方便称呼，把四个节点叫 A(3)、B(5)、C(7)、D(9)。
without(A, 2)
A is not empty, i=2 ≠ 0 → 走 else 分支
需要 without(B, 1) 的结果
│
└─ without(B, 1)
B is not empty, i=1 ≠ 0 → 走 else 分支
需要 without(C, 0) 的结果
│
└─ without(C, 0)
C is not empty, i=0 → 走 elif 分支
直接返回 C.rest，也就是节点 D 本身
⇒ 返回 D = Link(9) ← 这是原表里的 D，没有复制
拿到 D，构造新节点 B' = Link(B.first, D) = Link(5, Link(9))
⇒ 返回 B'
拿到 B'，构造新节点 A' = Link(A.first, B') = Link(3, Link(5, Link(9)))
⇒ 返回 A'
回显时调用 repr(A')，递归地得到 Link(3, Link(5, Link(9)))——与 doctest 一致。
再看内存里发生了什么。调用结束后的盒子指针图（' 表示新建节点）：
原表 s ──▶ A(3) ──▶ B(5) ──▶ C(7) ──▶ D(9) ──▶ Link.empty
▲
新表 ──▶ A'(3) ─▶ B'(5) ──────────────┘
新建了 2 个节点：A' 和 B'
共享了 1 个节点：D（新表和原表都指着同一个 D）
绕过了 1 个节点：C（新表里没有它，原表里它还在）
原表 A、B、C、D 的 first/rest 全部未被写入 ⇒ s 完好无损
再验证越界的第三个 doctest，without(s, 4)：
without(A, 4) → else → Link(3, without(B, 3)) without(B, 3) → else → Link(5, without(C, 2)) without(C, 2) → else → Link(7, without(D, 1)) without(D, 1) → else → Link(9, without(Link.empty, 0)) without(Link.empty, 0) → 第一个分支命中 → Link.empty 逐层回代： without(D, 1) = Link(9) without(C, 2) = Link(7, Link(9)) without(B, 3) = Link(5, Link(7, Link(9))) without(A, 4) = Link(3, Link(5, Link(7, Link(9)))) ✓
注意这一趟走下来 i 一直没归零，所以每个节点都走 else 分支被复制了一份。结果是一个和 s 内容相同但节点全新的链表——恰好符合「返回新表且保留全部元素」。同时也说明：without(s, 4) is s 会是 False，但 doctest 只看 repr，所以通过。
顺带做一次复杂度分析：设表长 n，函数最多递归 min(i, n) + 1 层，每层 $\Theta(1)$ 工作，所以时间是 $\Theta(\min(i, n))$，新建节点数同量级，空间也是 $\Theta(\min(i, n))$。相比「先整体复制再删」的 $\Theta(n)$，共享尾巴省下的是实打实的。
误区一：在 else 分支里写 s.rest = without(s.rest, i - 1); return s。 这样「省」掉了新建节点，但它就地改写了原表。运行 doctest 时第一条 without(s, 0) 还能过，第二条 without(s, 2) 就会在一个已经被破坏的 s 上跑，输出对不上。可变数据 + 复用输入 = 隐蔽的 bug，这是 61A 反复敲打的点。
误区二：忘记 Link.empty 分支，只写 i == 0 和 else。 前两条 doctest 会通过，第三条 without(s, 4) 会在走到表尾后继续访问 ().first，报 AttributeError: 'tuple' object has no attribute 'first'。这就是为什么题面要专门给一条越界的 doctest。
误区三：return Link(s.first, without(s.rest, i))，忘了减一。 这样 i 永远不会归零（除非一开始就是 0），函数会把整个表复制一遍，什么都没删。写递归时问自己：每一层递归调用，参数是否都朝着 base case 前进了？ 这里「前进」有两条腿——表在变短、i 在变小，缺一条都可能不停。
3. Duplicate Link duplicate_link
题目要什么
写 duplicate_link(s, val)：就地修改链表 s，让每一个等于 val 的元素后面紧跟一个新的 val（即复制一份）。函数返回 None。题面还警告了一句：小心别陷入「不断复制自己刚复制出来的副本」的死循环。
>>> x = Link(5, Link(4, Link(5)))
>>> duplicate_link(x, 5)
>>> x
Link(5, Link(5, Link(4, Link(5, Link(5)))))
>>> y = Link(2, Link(4, Link(6, Link(8))))
>>> duplicate_link(y, 10)
>>> y
Link(2, Link(4, Link(6, Link(8))))
>>> z = Link(1, Link(2, Link(2, Link(3))))
>>> duplicate_link(z, 2) # ensures that back to back links with val are both duplicated
>>> z
Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
这道题和 Q2 是镜像关系，务必对照着理解：
Q2 without | Q3 duplicate_link | |
|---|---|---|
| 对原表 | 绝对不能改 | 必须改，而且只能改它 |
| 返回值 | 新链表 | None（没有 return 语句） |
| 典型写法 | 递归构造 | 迭代改指针（递归也行） |
| 正确性怎么看 | 看返回的表 | 看调用之后原来那个名字指向的表 |
三条 doctest 各自在考什么，逐条点破：
x = Link(5, Link(4, Link(5)))，复制 5。考的是基本功能，而且要求表尾的那个 5 也要被复制（很多人写完发现最后一个漏了）。y 里根本没有 10。考的是一个都不匹配时不能出错、不能改动。z = Link(1, Link(2, Link(2, Link(3))))，复制 2。注释写得很明白：“ensures that back to back links with val are both duplicated”。两个相邻的 2 必须各自被复制一份，最终有四个 2。这条是整道题的关键测试——它同时排除了「跳得太多导致漏掉后一个」和「跳得太少导致死循环」两种错法。duplicate_link(x, 5) 那一行下面是空的
doctest 里 >>> duplicate_link(x, 5) 之后没有期望输出，这意味着这个调用必须返回 None（交互式解释器对 None 不显示任何东西）。如果你手贱在末尾加了 return s，doctest 会报 “Expected nothing, got Link(...)” 而失败。「改还是返」要选一个，不要既改又返——这是 61A 一贯的风格要求。
怎么想到的
第一步先明确「在链表中间插入一个节点」这个原子操作长什么样。假设当前站在节点 s 上，想在它后面插一个值为 val 的新节点：
插入前： s ──▶ [val | ●] ──▶ [下一个节点 ...]
第 1 步：记住原来的后继
rest_of_list = s.rest
第 2 步：造一个新节点，让它的 rest 指向原来的后继
new = Link(val, rest_of_list)
第 3 步：把 s 的 rest 改成指向新节点
s.rest = new
插入后： s ──▶ [val | ●] ──▶ [val | ●] ──▶ [下一个节点 ...]
原节点 新节点
顺序不能颠倒：如果先做 s.rest = Link(val)，原来的后继就没人指着了，整条尾巴当场丢失。改指针之前必须先把要覆盖掉的那个指针存下来——这是链表操作的第一条铁律。
好，插入会写了。现在的问题是遍历时怎么走。
弯路一：无脑 s = s.rest。 写成这样：
# 错误示范
while s is not Link.empty:
if s.first == val:
s.rest = Link(val, s.rest)
s = s.rest # ← 只往前走一格
推演一下 x = Link(5, ...)：站在第一个 5 上，插入一个新的 5，然后 s = s.rest 走到刚插入的那个新 5。新 5 的 first 也等于 val，于是又插一个……无限循环，程序卡死，最后 MemoryError 或者直接把机器内存吃光。这正是题面警告的那个坑。
弯路二：跳两格，但跳错了对象。 意识到要跳过副本，于是改成：
# 仍然有问题的示范
while s is not Link.empty:
if s.first == val:
s.rest = Link(val, s.rest)
s = s.rest.rest # 跳过新插入的那个
else:
s = s.rest
这一版其实是正确的（s.rest 是新节点，s.rest.rest 是原来的后继）。但它有个隐患：s.rest.rest 这个表达式必须在赋值之后才成立，读代码的人得在脑子里重放一遍赋值才能确认，容易写反成 s = s.rest 或者 s = s.rest.rest.rest。
最终写法：先把「原来的后继」存进一个有名字的变量，然后直接跳到它。 这样「跳到哪」是显式的、不依赖中间状态：
rest_of_list = s.rest 这个变量一石二鸟：(a) 它是新节点的 rest，保证尾巴不丢；(b) 它同时也正是「处理完这两个 val 之后应该继续的地方」。所以插完直接 s = rest_of_list，一步到位跳过原节点和副本两个。
为什么跳过两个是对的、而不是漏处理？因为副本的值就是 val，如果不跳过它会被再次复制；而原节点已经处理完了。至于 rest_of_list 那个节点——它没有被跳过，循环下一轮正好站在它上面。所以 z 里两个相邻的 2 都会被各自处理，得到四个 2。
代码
def duplicate_link(s: Link, val: int) -> None:
"""Mutates s so that each element equal to val is followed by another val.
>>> x = Link(5, Link(4, Link(5)))
>>> duplicate_link(x, 5)
>>> x
Link(5, Link(5, Link(4, Link(5, Link(5)))))
>>> y = Link(2, Link(4, Link(6, Link(8))))
>>> duplicate_link(y, 10)
>>> y
Link(2, Link(4, Link(6, Link(8))))
>>> z = Link(1, Link(2, Link(2, Link(3))))
>>> duplicate_link(z, 2) # ensures that back to back links with val are both duplicated
>>> z
Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
"""
while s is not Link.empty:
if s.first == val:
# Splice a copy of val in right after the current node, then jump
# past BOTH copies so we never duplicate the copy we just inserted.
rest_of_list = s.rest
s.rest = Link(val, rest_of_list)
s = rest_of_list
else:
s = s.rest
while s is not Link.empty: —— 标准的链表遍历循环。s 是局部形参，在函数里给它重新赋值只是让这个局部名字指向别的节点，不会影响调用者的 x。调用者的 x 始终指着第一个节点。这就是为什么函数能「修改链表」却不需要返回值：我们改的是节点对象内部的 rest 属性，而 x 指着的那个头节点从未被替换。if s.first == val: —— 这里用 == 而不是 is，因为比的是值。val 是数字，小整数在 CPython 里会被缓存所以 is 碰巧也能过，但大整数（如 1000）用 is 就可能失败。比值用 ==，比对象身份用 is——Q5 里正好是反过来的场景。rest_of_list = s.rest —— 在覆盖 s.rest 之前先存下来。这一行如果删掉，下一行就得写成 s.rest = Link(val, s.rest)，靠 Python「右边先求值」的规则侥幸正确；能工作，但不如显式变量清楚，而且第三行也没法写了。s.rest = Link(val, rest_of_list) —— 新节点的 first 用的是 val 而不是 s.first。这两者此刻相等，用哪个都对；写 val 更直白地表达了「我插的是那个被找的值」。s = rest_of_list —— 越过原节点和副本，落在原来的后继上。这一行是整道题的答案。 它保证了：副本不会被再处理（避免死循环），后继会被处理（相邻的 val 不漏）。else: s = s.rest —— 不匹配就正常前进一格。return 语句，所以自动返回 None，满足签名 -> None 和 doctest 的「无输出」要求。验证
手动追踪第三条 doctest：z = Link(1, Link(2, Link(2, Link(3))))，duplicate_link(z, 2)。四个原始节点记为 P(1)、Q(2)、R(2)、S(3)。
初始： z ──▶ P(1) ──▶ Q(2) ──▶ R(2) ──▶ S(3) ──▶ empty
s = P
第 1 轮 s = P，P.first = 1 ≠ 2 → else 分支
s = P.rest = Q
链表未变
第 2 轮 s = Q，Q.first = 2 == 2 → if 分支
rest_of_list = Q.rest = R
Q.rest = Link(2, R) ← 新节点记作 Q'
s = rest_of_list = R
此刻：z ─▶ P(1) ─▶ Q(2) ─▶ Q'(2) ─▶ R(2) ─▶ S(3) ─▶ empty
▲
s 站在这里（不是 Q'）
第 3 轮 s = R，R.first = 2 == 2 → if 分支
rest_of_list = R.rest = S
R.rest = Link(2, S) ← 新节点记作 R'
s = rest_of_list = S
此刻：z ─▶ P(1) ─▶ Q(2) ─▶ Q'(2) ─▶ R(2) ─▶ R'(2) ─▶ S(3) ─▶ empty
第 4 轮 s = S，S.first = 3 ≠ 2 → else 分支
s = S.rest = Link.empty
第 5 轮 循环条件 s is not Link.empty 为假 → 退出，函数返回 None
最终 z 指着 P，链表内容是 1, 2, 2, 2, 2, 3。repr 递归展开得到：
Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
与 doctest 完全一致。特别注意第 2 轮结束时 s 落在 R 而不是 Q'——正因如此，R 在第 3 轮被独立处理了一次，这才凑齐了四个 2。如果第 2 轮写成 s = s.rest（落在 Q'），Q' 又会被复制，无限下去。
再快速验证第二条 doctest duplicate_link(y, 10)：y 里的 2、4、6、8 没有一个等于 10，每轮都走 else，四轮后 s 变成 Link.empty 退出。全程没有执行过任何属性赋值，链表一个字节都没改，repr 输出与原来相同。
复杂度：设原表长 n、其中有 k 个元素等于 val。循环访问的节点数是 n（副本被跳过了，一个都没重复访问），每轮 $\Theta(1)$，所以时间 $\Theta(n)$。额外空间除了 k 个必须新建的节点外是 $\Theta(1)$——没有辅助列表、没有递归栈。这正是链表擅长的场景：在已经走到的位置插入元素是 $\Theta(1)$，换成 Python 的 list 做同样的事，每次 insert 都要挪动后面所有元素，总共是 $\Theta(n \cdot k)$。
误区一：s.rest = Link(val)，忘了接尾巴。 新节点的 rest 用了默认值 Link.empty，于是链表在这里被截断了，后面的所有元素全部丢失。x 那条会输出 Link(5, Link(5))，doctest 直接对不上。改指针必先存旧值。
误区二：s = s.rest 一路走到底。 前面详细推演过：程序会卡住不动，等一会儿抛 MemoryError，或者在 ok 里表现为测试超时。如果你运行 ok 时发现某个测试一直转圈不出结果，八成就是这里。
误区三：末尾加了 return s。 doctest 报 Expected: (nothing) / Got: Link(5, Link(5, ...))。题目说了返回 None 就是 None。
误区四：想用递归但写成 duplicate_link(s.rest, val) 却在匹配时递归到副本上。 递归版是可以写的，正确的递归调用应该是 duplicate_link(rest_of_list, val)（跳过副本），和迭代版逻辑完全一样。但递归版会占 $\Theta(n)$ 栈空间，而这道题本质上是「一路向前、无需回溯」，用循环更贴合。需要「回代」才用递归；只是「走一遍」就用循环。
4. Slice slice_link
题目要什么
实现 slice_link(link, start, end)，效果和 Python 列表切片 lst[start:end] 一样：取从下标 start 开始、到下标 end 前一个为止的那一段，返回一个新链表，不修改原链表。不需要支持负下标。
>>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
>>> new = slice_link(link, 1, 4)
>>> print(new)
(1 4 1)
>>> print(slice_link(link, 0, 2))
(3 1)
>>> print(slice_link(link, 0, 6))
(3 1 4 1 5 9)
>>> print(slice_link(link, 2, 2))
()
>>> print(slice_link(link, 2, 3))
(4)
>>> print(slice_link(link, 3, 100))
(1 5 9)
>>> print(slice_link(link, 10, 12))
()
七条 doctest，每一条都在钉死一种边界。把它们摊开看：
| 调用 | 期望 | 它在考什么 |
|---|---|---|
slice_link(link, 1, 4) | (1 4 1) | 普通情况：取下标 1、2、3，不含 4（左闭右开） |
slice_link(link, 0, 2) | (3 1) | start = 0，从头开始 |
slice_link(link, 0, 6) | (3 1 4 1 5 9) | end 正好等于长度，取全部 |
slice_link(link, 2, 2) | () | start == end，空切片 |
slice_link(link, 2, 3) | (4) | 只取一个元素 |
slice_link(link, 3, 100) | (1 5 9) | end 远超长度，取到表尾为止就停 |
slice_link(link, 10, 12) | () | start 就已经越界，整段都取不到 |
() 是打印出来的 Link.empty
print(slice_link(link, 2, 2)) 输出 ()——这不是 Link.__str__ 生成的，因为 Link.empty 根本不是 Link 实例，它就是那个空元组，print(()) 自然打出 ()。所以「返回空切片」在这道题里的正确做法就是 return Link.empty。如果你返回 None，会打出 None，测试挂掉。
怎么想到的
这道题的骨架和 Q2 without 是同一个模子——都是「递归地构造新链表」——但多了一个参数需要照顾。先建立正确的心理模型。
第一个念头：先跳 start 步，再拷 (end - start) 个。 这个想法本身没错，而且很自然，写出来大概是：
# 思路草稿（不是最终代码）
def slice_link(link, start, end):
# 阶段一：跳过前 start 个
while start > 0 and link is not Link.empty:
link = link.rest
start, end = start - 1, end - 1
# 阶段二：拷贝接下来的 end 个
...
问题出在阶段二：迭代地「拷贝一段并保持顺序」需要维护头指针和尾指针，还要处理「新表为空」的第一步，很啰嗦。而且这两个阶段其实是同一件事的两种状态，硬拆成两段反而绕。
转向：把「我现在处于哪个阶段」编码进参数本身。
关键洞察是：start 和 end 是相对于当前 link 的下标，不是相对于最初那个表的绝对下标。每往后走一个节点，当前节点在剩余表里的编号就少 1，所以start 和 end 要同时减 1。有了这个约定，函数任何时刻的状态都能只看这三个参数读出来：
start > 0：窗口还没开始，当前元素在窗口左边，扔掉它，继续看 link.rest，同时 start - 1、end - 1。start <= 0 且 end > 0：当前元素在窗口内，复制它，然后继续看 link.rest。此时 start 已经归零，后面一直保持 0 即可（所以递归调用里直接写死 0），end 继续减 1 表示「还能再要几个」。end <= 0：窗口已经关闭，后面一个都不要了，返回 Link.empty。link is Link.empty：表走完了，无论窗口开没开、关没关，都没有东西可取，返回 Link.empty。end 从「绝对终点」变成「还能再要几个」
一旦 start 归零进入窗口内，end 的含义就自动变成了「剩余配额」——因为窗口长度 = end - start，而 start = 0 时它就等于 end。所以整个函数只需要一个终止条件 end <= 0，不需要额外的计数器。把两个不同阶段的语义统一到同一组参数上，是这道题最漂亮的地方。
为什么写 end <= 0 而不是 end == 0？因为 slice_link(link, 10, 12) 这种情况下，start 会先归零……不，实际上表只有 6 个元素，走到第 6 步表就空了，先命中 link is Link.empty。但考虑 slice_link(link, 5, 3) 这类 start > end 的输入：end 会先减到 0 以下。用 <= 是防御性的——判断条件宁可宽一点，也不要留下一个「恰好跳过」的缝隙让程序无限递归下去。
代码
def slice_link(link: Link, start: int, end: int) -> Link:
"""Slices a linked list from start to end (as with a normal Python list) and returns
a linked list. You do NOT have to support negative indices.
>>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
>>> new = slice_link(link, 1, 4)
>>> print(new)
(1 4 1)
>>> print(slice_link(link, 0, 2))
(3 1)
>>> print(slice_link(link, 0, 6))
(3 1 4 1 5 9)
>>> print(slice_link(link, 2, 2))
()
>>> print(slice_link(link, 2, 3))
(4)
>>> print(slice_link(link, 3, 100))
(1 5 9)
>>> print(slice_link(link, 10, 12))
()
"""
if link is Link.empty or end <= 0:
# No elements left, or the slice window has closed.
return Link.empty
elif start > 0:
# Haven't reached the start of the window yet: discard this element and
# shift both bounds one step left.
return slice_link(link.rest, start - 1, end - 1)
else:
# Inside the window: copy this element and keep going.
return Link(link.first, slice_link(link.rest, 0, end - 1))
if link is Link.empty or end <= 0: —— 两个 base case 合并成一个分支，因为它们的返回值相同。link is Link.empty 必须放在最前面：后面两个分支都要访问 link.rest 或 link.first，在空表上会 AttributeError。or 有短路特性，但这里两个操作数都不会出错，顺序只影响可读性。elif start > 0: —— 「还没到窗口」。返回值直接是递归调用的结果，没有包一层 Link(...)——因为当前元素不属于切片，要被丢掉。这一步是纯粹的前进，不产生任何新节点。slice_link(link.rest, start - 1, end - 1) —— 两个边界都减 1，这是整道题最容易写错的一行。只减 start 不减 end，窗口就会被拉长成 end - 0 个元素而不是 end - start 个。用 slice_link(link, 1, 4) 一验就露馅：会输出 (1 4 1 5)，多一个。else: —— 走到这里意味着 link 非空、end > 0、start <= 0，三个条件合起来就是「在窗口内」。return Link(link.first, slice_link(link.rest, 0, end - 1)) —— 新建节点保证不动原表（和 Q2 同理）。递归调用第二个参数写死 0：因为一旦进入窗口就永远在窗口内了，start 不该再变负；写 start - 1 也能过测试（负数同样满足 start > 0 为假），但写 0 更明确地表达了「start 这个变量已经完成使命」。end - 1 —— 配额用掉一个。当配额耗尽，下一层就命中第一个分支返回 Link.empty，成为新链表的末端。这个 Link.empty 就是新表的收尾，所以我们造出的切片是一条完全独立的新链，和原表不共享任何节点。without 在 i == 0 时直接 return s.rest，与原表共享尾巴；slice_link 则一个节点都不共享，全是新建的。原因是切片的末端必须是 Link.empty，而原表在那个位置往往还有后续元素，所以无法共享。验证
手动追踪第一条 doctest：link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))，求 slice_link(link, 1, 4)。六个节点按下标记为 n0(3)、n1(1)、n2(4)、n3(1)、n4(5)、n5(9)。
slice_link(n0, 1, 4)
n0 非空，end=4>0，start=1>0 → elif 分支（丢掉 3）
= slice_link(n1, 0, 3)
n1 非空，end=3>0，start=0 不>0 → else 分支（保留 1）
= Link(1, slice_link(n2, 0, 2))
n2 非空，end=2>0，start=0 → else（保留 4）
= Link(4, slice_link(n3, 0, 1))
n3 非空，end=1>0，start=0 → else（保留 1）
= Link(1, slice_link(n4, 0, 0))
n4 非空，但 end=0 <= 0 → 第一个分支
= Link.empty
逐层回代：
slice_link(n4, 0, 0) = Link.empty
slice_link(n3, 0, 1) = Link(1, Link.empty) = Link(1)
slice_link(n2, 0, 2) = Link(4, Link(1))
slice_link(n1, 0, 3) = Link(1, Link(4, Link(1)))
slice_link(n0, 1, 4) = Link(1, Link(4, Link(1))) ← 同上，因为 elif 不包装
结果链表是三个新建节点，内容 1, 4, 1。print 调用 __str__：循环把 '1 '、'4 ' 拼进去，退出时补 '1)'，得到 (1 4 1)。与 doctest 一致。
原表 link ─▶ n0(3) ─▶ n1(1) ─▶ n2(4) ─▶ n3(1) ─▶ n4(5) ─▶ n5(9) ─▶ empty
└────窗口 [1, 4) 覆盖 n1 n2 n3────┘
新表 new ─▶ m0(1) ─▶ m1(4) ─▶ m2(1) ─▶ Link.empty
全部是新建节点，与原表零共享；原表未被写入任何属性
再追两条边界情况，确认设计站得住：
【slice_link(link, 2, 2) 期望 ()】
slice_link(n0, 2, 2) n0 非空, end=2>0, start=2>0 → elif
= slice_link(n1, 1, 1) n1 非空, end=1>0, start=1>0 → elif
= slice_link(n2, 0, 0) n2 非空, 但 end=0 <= 0 → 第一分支
= Link.empty
print(Link.empty) 就是 print(()) → 输出 () ✓
关键：两个边界同步减，所以 start 归零的同时 end 也归零，窗口宽度 0。
【slice_link(link, 3, 100) 期望 (1 5 9)】
slice_link(n0, 3, 100) → elif → slice_link(n1, 2, 99)
→ elif → slice_link(n2, 1, 98)
→ elif → slice_link(n3, 0, 97)
n3 起进入窗口：
= Link(1, slice_link(n4, 0, 96))
= Link(1, Link(5, slice_link(n5, 0, 95)))
= Link(1, Link(5, Link(9, slice_link(Link.empty, 0, 94))))
└─ link is Link.empty → Link.empty
= Link(1, Link(5, Link(9)))
print → (1 5 9) ✓
关键：end=94 还剩很多配额，但表已经走完，靠 link is Link.empty 兜住。
【slice_link(link, 10, 12) 期望 ()】
连续 6 次 elif 后 link 变成 Link.empty（此时 start=4, end=6）
→ 第一分支 → Link.empty → 输出 () ✓
这三条合起来说明：两个 base case 缺一不可。end <= 0 管「要够了」，link is Link.empty 管「没了」。少写任何一个，都会有 doctest 挂掉。
复杂度：递归层数最多是 min(end, n) + 1，每层 $\Theta(1)$，时间 $\Theta(\min(end, n))$；新建节点数是切片长度，递归栈深度同上，所以空间也是 $\Theta(\min(end, n))$。
误区一：elif start > 0: return slice_link(link.rest, start - 1, end)——只减 start。 这是这道题最高频的错误。slice_link(link, 1, 4) 会输出 (1 4 1 5)，多取一个。原因是当 start 归零时 end 还停在 4，被当成「还能要 4 个」，而正确答案是 4 - 1 = 3 个。只要移动了当前位置，所有相对于当前位置的下标都必须同步平移。
误区二：漏掉 link is Link.empty 分支。 前六条 doctest 里有五条能过，但 slice_link(link, 3, 100) 会在走完表以后继续 link.first，报 AttributeError: 'tuple' object has no attribute 'first'。而 slice_link(link, 10, 12) 则会在 elif 分支里 ().rest 崩掉。
误区三：else 分支里写成 link.rest = slice_link(...) 或者返回 link 本身。 这会破坏原表。因为 doctest 里 link 被连续切了七次，第一次切完如果改了原表，后面六条全会错乱。题目明说 “this function should return a new list and not modify the original list”。
误区四：base case 返回 None 而不是 Link.empty。 上一层的 Link(link.first, None) 会触发构造器的 assert rest is Link.empty or isinstance(rest, Link)，抛 AssertionError。这时候你应该庆幸有那个 assert——否则你会在某个 print 里看到莫名其妙的 AttributeError，还得倒推半天。
5. Cycles has_cycle
题目要什么
Link 类可以表示带环的链表——某个节点的 rest 指回了前面已经出现过的节点，于是这条链没有终点。题面给的例子：
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3
写 has_cycle(link)，返回这个链表里有没有环。题面给的提示是：遍历链表，同时记录你已经见过哪些 Link 对象。
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle(t)
False
>>> u = Link(2, Link(2, Link(2)))
>>> has_cycle(u)
False
三条 doctest 的分工：第一条是有环，第二条是普通无环，第三条是整道题的陷阱——u 里三个节点的 first 都是 2，值完全相同，但它们是三个不同的对象，链表照样在第三个节点后终止于 Link.empty。答案必须是 False。
判断有没有环，唯一的依据是「我是不是又回到了同一个 Link 对象」。两个节点的 first 相等说明不了任何问题；哪怕整条链表所有元素都一样，只要每个节点是独立分配的对象，它就没有环。所以这道题从头到尾只能用 is，绝不能用 ==。
再补一句为什么这个函数有存在价值：Q1 里我们见过，环形链表调 print() 会永远转下去。任何遍历链表的函数（包括你自己写的 without、slice_link）遇到环都会挂死。has_cycle 是防御性的工具。
怎么想到的
第一个念头（多半是错的）：走很多步，如果一直没到 Link.empty 就算有环。 比如「走 10000 步还没结束就返回 True」。这是启发式不是算法：一条长度 20000 的正常链表会被误判为有环。魔法数字解决不了正确性问题，必须找一个真正的判据。
第二个念头（正确，也是题面提示的）：记账。 环意味着「我第二次踩到了同一块石头」。那就把踩过的石头全记下来，每到一个新节点先查一查在不在名单里：
- 在名单里 → 说明绕回来了 → 有环，返回
True； - 不在 → 记上，继续走；
- 一直走到
Link.empty→ 链表有终点 → 无环，返回False。
为什么这个算法一定会终止？因为链表里的节点数是有限的（设为 n）。如果有环，最多走 n + 1 步必然重复；如果无环，最多走 n 步就到 Link.empty。两种情况都会停。
接下来是这道题真正的技术难点：怎么查「在不在名单里」。
弯路：写 if link in seen:。 看起来天经地义，但 in 运算符对列表的语义是「存在某个元素 x 使得 x is link or x == link」。Python 会先试 is，不成再试 ==。Link 类没有定义 __eq__，所以 == 退化成身份比较，in 碰巧也能给出正确答案。但这是依赖运气：一旦有人给 Link 加上一个按值比较的 __eq__，第三条 doctest 立刻挂掉（三个 Link(2, ...) 会被认为相等）。既然我们心里清楚要比的是身份，就应该把这个意图写进代码里。
any(...) 显式地做身份比较
any(link is node for node in seen) 逐个用 is 比对，只要有一个是同一个对象就返回 True。它和 link in seen 在当前实现下结果相同，但意图是明确的、不依赖 Link 有没有 __eq__。这就是所谓「让代码说出你真正的意思」。
代码
def has_cycle(link: Link) -> bool:
"""Return whether link contains a cycle.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle(t)
False
>>> u = Link(2, Link(2, Link(2)))
>>> has_cycle(u)
False
"""
seen = [] # Every Link object we have already visited.
while link is not Link.empty:
# Compare by identity: two different Links may hold equal values.
if any(link is node for node in seen):
return True
seen.append(link)
link = link.rest
return False # Reached Link.empty, so the list ends.
seen = [] —— 一个普通 Python 列表，存的是Link 对象本身的引用，不是它们的值。这是本函数唯一的额外空间。while link is not Link.empty: —— 无环时这个条件负责终止；有环时它永远为真，靠循环体里的 return True 跳出。两条出口各管一种情况。if any(link is node for node in seen): return True —— 检查必须放在 append 之前。如果顺序反了，先把自己加进去再查，那么每个节点第一次访问时就会在名单里找到它自己，函数对任何非空链表都返回 True。seen.append(link) —— 记账。注意 append 存的是引用，不复制节点。link = link.rest —— 前进。link 是形参，重新绑定它不会影响调用者，也不修改任何节点——这个函数是只读的，一个属性都没写。return False —— 循环正常结束（走到了 Link.empty），说明链表有终点。这一行必须在 while 外面；写在里面（缩进多一级）会让函数第一轮就返回，只有第一条 doctest 侥幸通过。验证
先追踪有环的 s。执行 s.rest.rest.rest = s 之后的结构：
s ──▶ ┌──────┐ ┌──────┐ ┌──────┐
│ A: 1 │───▶│ B: 2 │───▶│ C: 3 │───┐
└──────┘ └──────┘ └──────┘ │
▲ │
└────────────────────────────────┘
C.rest 指回 A，形成一个长度为 3 的环，没有 Link.empty
seen = [] link = A
第 1 轮 A is not empty → 进入循环
any(A is node for node in []) → False（空序列，any 返回 False）
seen = [A]
link = A.rest = B
第 2 轮 B is not empty
any(B is node for node in [A]) → B is A 为 False → False
seen = [A, B]
link = B.rest = C
第 3 轮 C is not empty
any(C is node for node in [A, B]) → 都不是 → False
seen = [A, B, C]
link = C.rest = A ← 绕回起点
第 4 轮 A is not empty
any(A is node for node in [A, B, C]) → 第一个就命中 A is A → True
return True ✓
再追踪无环的 t = Link(1, Link(2, Link(3)))，节点记为 P、Q、R：
第 1 轮 link=P，not in [] → seen=[P]，link=Q
第 2 轮 link=Q，not in [P] → seen=[P,Q]，link=R
第 3 轮 link=R，not in [P,Q] → seen=[P,Q,R]，link=R.rest=Link.empty
第 4 轮 循环条件 link is not Link.empty 为假 → 退出
return False ✓
第三条 u = Link(2, Link(2, Link(2))) 是最重要的验证。三个节点记为 U1、U2、U3，first 都是 2：
第 1 轮 link=U1，seen=[] → 无命中 → seen=[U1]，link=U2
第 2 轮 link=U2，seen=[U1]
判断 U2 is U1 → False
（注意：如果这里错用 U2.first == U1.first，会得到 2 == 2 → True
函数就会错误地返回 True）
→ seen=[U1,U2]，link=U3
第 3 轮 link=U3，seen=[U1,U2]
U3 is U1 → False；U3 is U2 → False
→ seen=[U1,U2,U3]，link=U3.rest=Link.empty
第 4 轮 退出循环 → return False ✓
复杂度：设链表节点数 n。外层循环最多 n + 1 轮，每轮的 any(...) 要扫一遍 seen（长度最大 n），所以时间是 $\Theta(n^2)$，空间是 $\Theta(n)$。用 set 存 id(link) 可以把时间降到 $\Theta(n)$，但空间仍是 $\Theta(n)$——这正是下面那道选做题要攻克的地方。
选做：has_cycle_constant，只用常数空间
题面的额外挑战：不记录任何见过的节点，判断有没有环。解法不到 20 行，但需要一个巧妙的想法。
怎么想到的。 既然不能记账，就只能靠「走路」本身产生信息。想象一条环形跑道上有两个人，一个走得慢、一个走得快。如果跑道是直线（无环），快的那个先跑到终点，从此再也见不到慢的。如果跑道是环形（有环），两个人都会一直转下去，而快的会不断拉开距离——绕回来以后从后面追上慢的，最终必然在某一步踩到同一个位置。这就是 Floyd 的「龟兔赛跑」（tortoise and hare）算法。
为什么「必然踩到同一格」而不是「跨过去」？因为快指针每步比慢指针多走 1 格，所以它们之间的距离每步恰好缩小 1。一个每步减 1 的非负整数距离，一定会经过 0。如果快指针一次走 3 格，距离每步减 2，就可能在距离为 1 时跨过去——所以步长必须是 1 和 2。
def has_cycle_constant(link: Link) -> bool:
"""Return whether link contains a cycle.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle_constant(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle_constant(t)
False
"""
# Floyd's "tortoise and hare": slow advances one node per step, fast
# advances two. If there is a cycle, fast eventually laps slow and they
# land on the same object; if there is no cycle, fast falls off the end.
slow, fast = link, link
while fast is not Link.empty and fast.rest is not Link.empty:
slow = slow.rest
fast = fast.rest.rest
if slow is fast:
return True
return False
slow, fast = link, link —— 两个指针从同一个节点出发。必须先走再比，否则第一次比较时 slow is fast 立刻为真，任何链表都被判为有环。代码里的比较放在两次移动之后，正好满足这一点。while fast is not Link.empty and fast.rest is not Link.empty: —— 两个条件缺一不可，因为下一行要做 fast.rest.rest，需要保证 fast 和 fast.rest 都是真正的 Link。and 的短路在这里是必需的：如果 fast 已经是 Link.empty，右边的 fast.rest 会 AttributeError，全靠 and 不去求值它。这是「短路求值不只是优化，而是正确性前提」的经典例子。slow = slow.rest / fast = fast.rest.rest —— 慢的走一格、快的走两格。slow 不需要判空，因为它永远落在 fast 走过的路上，fast 能走两格就说明 slow 走一格安全。if slow is fast: return True —— 再次强调是 is：两个指针指向同一个对象才算相遇。return False —— fast 掉出表尾，说明有终点。空间只用了两个名字，$\Theta(1)$。时间仍是 $\Theta(n)$（无环时 fast 走 n/2 步到头；有环时相遇发生在 $O(n)$ 步内）。结构：A ─▶ B ─▶ C ─▶ A（回到 A）
初始 slow = A，fast = A
第 1 轮 条件：fast=A 非空，fast.rest=B 非空 → 进入
slow = A.rest = B
fast = A.rest.rest = C
B is C？ 否 → 继续
第 2 轮 条件：fast=C 非空，fast.rest=A 非空 → 进入
slow = B.rest = C
fast = C.rest.rest = A.rest = B
C is B？ 否 → 继续
第 3 轮 条件：fast=B 非空，fast.rest=C 非空 → 进入
slow = C.rest = A
fast = B.rest.rest = C.rest = A
A is A？ 是 → return True ✓
【对照无环的 t：P ─▶ Q ─▶ R ─▶ empty】
初始 slow = P，fast = P
第 1 轮 fast=P 非空，fast.rest=Q 非空 → 进入
slow = Q，fast = P.rest.rest = R
Q is R？ 否
第 2 轮 fast=R 非空，但 fast.rest = R.rest = Link.empty
第二个条件为假 → 退出循环
return False ✓
误区一：用 == 或者比 first。 写成 if link.first in [n.first for n in seen]，第三条 doctest u = Link(2, Link(2, Link(2))) 会返回 True，而正确答案是 False。这条 doctest 就是专门为了抓这个错而存在的。
误区二：seen.append 写在检查之前。 每个节点一进来就发现自己在名单里，函数对所有非空链表返回 True。第二、三条 doctest 挂掉。
误区三：快慢指针的 while 条件只写 fast is not Link.empty。 当 fast 走到最后一个节点（fast.rest 是 Link.empty）时，fast.rest.rest 变成 ().rest，报 AttributeError: 'tuple' object has no attribute 'rest'。奇数长度和偶数长度的链表在这里表现不同，只测一个长度很容易漏掉。
误区四：快慢指针初始化成 slow, fast = link, link.rest 并把比较放在循环开头。 这个变体也能工作（很多教科书就这么写），但如果你在初始化时写了 link.rest 而 link 恰好是 Link.empty，就会当场崩。本仓库的写法从同一点出发、先走后比，不需要对入参做特判，更稳。
误区五：以为 has_cycle 只需要检查 link.rest is link。 那只能查出长度为 1 的自环。环可以任意长，甚至可以是「一条直尾巴 + 末端一个环」的 ρ 形结构，必须用通用算法。
整份作业回顾
这次五道题看起来是五个孤立的函数，实际上它们围着同一根轴转：链表的定义是递归的，所以处理它的代码也是递归的；链表的节点是可变对象，所以「改」和「造」是两条完全不同的路，走错了就会互相污染。
| 题目 | 核心手法 | 迁移到哪里 |
|---|---|---|
| Q1 WWPD | 身份 vs 值；repr vs str；构造器 assert 作为不变量护栏 | 任何自定义类的调试；后面的 Tree、Scheme pair |
Q2 without | 递归构造新表；只复制会变的前缀，共享不变的尾巴 | 持久化数据结构；Scheme 里所有 list 操作的默认姿势 |
Q3 duplicate_link | 就地改指针；改之前先存旧值；跳过自己刚插入的节点 | 链表插入/删除/反转；任何「边遍历边修改」的场景 |
Q4 slice_link | 把「阶段」编码进参数；两个边界同步平移 | 带窗口/区间的递归；树的层级遍历；动态规划的下标管理 |
Q5 has_cycle | 用集合记账换正确性；Floyd 快慢指针用推理换空间 | 图的访问标记；找重复元素；判断迭代序列是否周期 |
真正学到的三件事
first + 递归处理 rest」。Q2 和 Q4 是同一个模板的两个实例，差别只在于「递归调用的结果要不要包一层 Link」。以后遇到树（Tree）、遇到 Scheme 的 pair，你会发现是同一件事。link = link.rest 只是让一个局部名字换个指向，调用者毫无感觉；link.rest = ... 才是真的写进了对象内部，全世界指着这个对象的人都会看到。Q3 之所以不需要返回值，正是因为它做的是后者；Q2 和 Q4 之所以必须 return，正是因为它们只做前者加上新建对象。写链表代码时，每写一行赋值都问自己：我改的是名字还是对象？is 与 == 的选择是有含义的，不是风格问题。 判断空表用 is Link.empty（因为空表是唯一的单例）；判断元素值用 ==（Q3 里 s.first == val）；判断有没有绕回同一个节点用 is（Q5）。Q5 的第三条 doctest 存在的唯一目的，就是把「用错了会怎样」摆到你面前。- 遍历链表：
while s is not Link.empty: ... ; s = s.rest - 递归骨架：先判
Link.empty，再判别的条件，最后Link(s.first, f(s.rest, ...)) - 插入节点：
rest_of_list = s.rest→s.rest = Link(v, rest_of_list)→ 想跳过副本就s = rest_of_list - 不修改原表：任何要改
rest的节点都得新建；不改的尾巴可以直接共享 - base case 返回
Link.empty，永远不要返回None（构造器的assert会替你抓住这个错） - 环检测：记账法 $\Theta(n)$ 空间简单可靠；Floyd 快慢指针 $\Theta(1)$ 空间，
while fast is not Link.empty and fast.rest is not Link.empty两个条件缺一不可
本地验证
在 labs/lab08/ 下运行 python3 ok --local，7 个测试用例全部通过：Q1 的三组 WWPD（tests/link.py 中的三个 case，均已解锁为明文），加上 without、duplicate_link、slice_link、has_cycle 的函数测试，以及选做的 has_cycle_constant。本页贴出的每一段代码都与 labs/lab08/lab08.py 中的真实文件逐字一致。