Hello 算法（俄文版）：数组与链表章节练习题精讲——从按位访问、插入扩容到反转链表

本篇基于《Hello 算法》俄文版第 2 章「Массивы и списки（数组与列表）」的练习页（exercises.md）展开。你将完整继承原文档的三组自检问题与答案解析，并结合仓库中 linked_list.py、my_list.py、array.py 三份可运行源码，把「为什么数组按位访问是 O(1)」「链表插入为何要先存后接」「动态扩容为什么看起来容量在增长」这些结论落到代码层面，最后通过「大数加一」与「反转链表」两道编程题训练对两类结构的实际操控能力。

一、自检问题：数组与链表如何查找元素

题目设定

在数组和单链表中按顺序存储着 [A, B, C, D, E]，要求读取第 4 个元素 D。原文档提出三个子问题：

1. 在数组中可以直接使用哪个索引？
2. 在单链表中，从头节点 A 出发，需要沿 next 依次经过哪些节点？
3. 当目标元素离头部越远时，两种结构各需要多少步？哪种结构更适合多次按位置访问，为什么？

参考答案

1. 若索引从 0 开始，第 4 个元素的索引是 3，因此数组中可以直接访问 arr[3]。
2. 单链表必须从头节点出发，路径为 A → B → C → D，即需要沿 next 移动 3 次。
3. 数组可以根据起始地址加索引直接定位元素，按位置访问的时间复杂度为 $O(1)$。而要访问单链表的第 $k$ 个节点，需要从头部开始沿 next 走 $k-1$ 步，最坏情况下需要 $O(n)$ 时间。原文档特别提醒：这里只比较「按位置访问」这一项，并不意味着链表在所有操作上都更慢。

源码印证：链表访问确实是逐步遍历

仓库中的链表操作示例 linked_list.py 给出了 access 函数的实现，它正是上述结论的直观体现：

def access(head: ListNode, index: int) -> ListNode | None:
    """Доступ к узлу связного списка по индексу index"""
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head

从源码结构看，该函数用一个 for 循环恰好执行 index 次 head = head.next——访问第 4 个节点（index = 3）就是 3 步遍历，与练习题第 2 小问的答案 A → B → C → D 完全对应。而链表节点的定义见 list_node.py：每个节点只保存 val 与指向后继的 next 两个字段，没有下标概念，这正是「无法按位直达」的结构根源。对比之下，Python 的 list 支持 nums[1] 直接取值，驱动代码见 list.py。

二、自检问题：在数组和链表中插入元素

题目设定

数组和单链表中存储着 A, B, C, D，要求把 X 插入到 B 之后，且额外给定两个前提条件：

• 数组容量为 5，当前状态为 [A, B, C, D, _]（_ 表示空位）；
• 链表形态为 A → B → C → D，并且已经拿到了节点 B 的引用。

三个子问题：

1. 数组中哪些元素需要移动？插入后的数组是什么样？
2. X.next 与 B.next 应该按什么顺序修改？插入后的链表是什么样？
3. 为什么比较插入效率时必须强调「已持有节点 B 的引用」这一前提？

参考答案

1. 数组中需要先向右移动 D 一格，再移动 C 一格，最后把 X 放到索引 2。结果是 [A, B, X, C, D]。注意移动方向：从尾部向头部逆序搬移，避免元素被覆盖。
2. 初始时 B.next 指向 C。应先执行 X.next = B.next，让 X 指向 C；再执行 B.next = X。结果是 A → B → X → C → D。如果先改写 B.next 而没有保存原有的后继关系，就会丢失 C 及其之后的整段链表。
3. 若已知 B 的位置，链表插入只需改动两条指针，耗时 $O(1)$；但如果还要从头查找 B，查找本身就可能花费 $O(n)$ 时间。因此谈「链表插入是 O(1)」必须附带「已知插入点」这个前提。

源码印证：先存后继、后改指针的两步法

仓库 linked_list.py 中的 insert 函数把上述顺序固化成了两行核心代码：

def insert(n0: ListNode, P: ListNode):
    """Вставить узел P после узла n0 в связном списке"""
    n1 = n0.next   # 先缓存 n0 的旧后继（即题目中的 C）
    P.next = n1    # 第一步：X.next = B.next
    n0.next = P    # 第二步：B.next = X

对照练习题的记号：n0 就是 B，P 就是 X，n1 就是被临时保存下来的 C。三行代码严格遵循「先 X.next = B.next，再 B.next = X」的顺序——如果颠倒成先执行 n0.next = P，n1 = n0.next 之后拿到的就再也不是 C 而是 X 自己，链表后半段随即断链。这正印证了答案第 2 小问中「若先重写 B.next 而未保留旧连接，会丢失节点 C」的警告。

同样的「先移后放」思想也存在于数组一侧。array.py 的 insert 函数演示了数组插入的逆序搬移：

def insert(nums: list[int], num: int, index: int):
    """Вставить элемент num по индексу index в массив"""
    # Сдвинуть элемент с индексом index и все последующие элементы на одну позицию назад
    for i in range(len(nums) - 1, index, -1):
        nums[i] = nums[i - 1]
    nums[index] = num

循环 range(len(nums) - 1, index, -1) 从最后一个下标往回走，正是答案第 1 小问「先移 D、再移 C、最后放 X」的通用化写法；而封装在 MyList 类里的同一段逻辑见 my_list.py。

三、自检问题：列表的容量是如何增长的

题目设定

一个基于数组的列表当前包含 [A, B, C]，长度 size = 3，容量 capacity = 4。当空间不足时，新数组的容量按 2 倍 增长。

三个子问题：

1. 添加 D 之后，长度和容量各是多少？是否需要扩容？
2. 接着添加 E，容量变成多少？需要复制多少个旧元素？
3. 底层数组的长度是不可变的，为什么看起来列表的容量却能增长？

参考答案

1. D 恰好放进最后一个空位。内容变为 [A, B, C, D]，size = 4，capacity = 4，无需扩容。
2. 添加 E 时已无空位，需要新建容量为 8 的数组，把 4 个旧元素 A, B, C, D 全部复制过去，再放入 E。此后 size = 5，capacity = 8。
3. 原数组本身并不会变长。列表的做法是：创建一个更大的新数组、把旧元素复制过去、然后把新数组作为底层存储。对用户而言，容量就像「变大」了一样。

源码印证：MyList 的扩容机制

这一练习的设定与仓库中 MyList 类的默认参数一一对应。my_list.py 的构造函数：

def __init__(self):
    """Конструктор"""
    self._capacity: int = 10  # Вместимость списка
    self._arr: list[int] = [0] * self._capacity
    self._size: int = 0
    self._extend_ratio: int = 2  # Коэффициент увеличения списка при каждом расширении

其中 _extend_ratio = 2 正是题目中「容量翻倍」的由来。扩容的触发点与执行过程分布在两处：add 方法在追加前检查 self.size() == self.capacity()，一旦相等就调用 extend_capacity（见 my_list.py）；而扩容本体则是「新建更大数组 + 复制 + 换引用」三步走：

def extend_capacity(self):
    """Расширение списка"""
    # Создать новый массив длиной в _extend_ratio раз больше исходного массива
    # и скопировать в него исходный массив
    self._arr = self._arr + [0] * self.capacity() * (self._extend_ratio - 1)
    self._capacity = len(self._arr)

从源码结构看，self._arr + [0] * capacity * (ratio - 1) 生成了一个长度翻倍的新序列并整体替换 self._arr——旧的底层存储被丢弃，元素随复制迁移到新存储。这恰好把答案第 3 小问的抽象解释变成了可读代码：数组对象换了一个，所以「容量增长」只是对外呈现的效果，底层始终是「旧数组建新数组再复制」。

练习中 capacity = 4 的具体数字可以按同样规则推演：size 从 3 增到 4 时恰好填满、不触发扩容；再加 E 时 size == capacity 成立，触发一次翻倍（4 → 8），并复制全部 4 个旧元素。若把默认容量 10 的 MyList 当作参照，其驱动代码在连续 add 时会在长度超过 10 的那一刻打出扩容后的新容量（见 my_list.py 的 Driver Code）。

四、编程题：给数组表示的大数加一

题目描述（原文完整继承）

数组 digits 从左到右存放一个非负整数的各位数字，例如 [3, 0, 8] 表示 308。数字 0 表示为 [0]；其余输入的首位数字不为 0。

请模拟十进制竖式加法：把这个数加 1，并按同样的数组格式返回结果。可以直接修改 digits；如果最高位之前产生新的进位，可以返回一个更长的数组。

提示（原文完整继承）

1. 和竖式加法一样，从数组的最后一位数字开始处理；
2. 若当前位数字小于 9，将其加 1 并立即返回结果；
3. 若当前位数字等于 9，把它置 0；如果所有位都是 9，则在最前面补一个 1。

结合仓库的解法说明

这道题训练的是数组「逆序遍历 + 边界处理」的基本功，其逆序搬移手法与本章 insert/remove 的循环方向一致（参考 array.py）。按提示可写出如下参考实现：

def plus_one(digits: list[int]) -> list[int]:
    """把 digits 表示的整数加 1，按同样的数组格式返回"""
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:          # 提示 2：不足 9，直接 +1 结束
            digits[i] += 1
            return digits
        digits[i] = 0              # 提示 3：9 进位，本位置 0
    # 走到这里说明所有位都是 9，提示 3：最前面补 1
    return [1] + digits

要点解析：

• 逆序遍历：range(len(digits) - 1, -1, -1) 模拟竖式从个位开始相加，与练习三章强调的「从尾部向头部移动」是同一种数组操作范式。
• 两种提前退出：一旦遇到小于 9 的位，加 1 后返回，前面所有高位不变，平均只需走一位到少数几位的扫描；只有全 9 的情况才走满 $O(n)$ 并在头部插入 1，产生更长的数组。
• 头部插入代价：[1] + digits 相当于在索引 0 处插入，对应练习二中数组插入「整体右移」的 $O(n)$ 代价——这也再次说明数组「访问快、中间插入慢」的特性。

五、编程题：反转单链表

题目描述（原文完整继承）

给定单链表的头节点 head。每个节点包含一个值和一个指向下一个节点的 next 字段。

请用迭代方式反转节点之间的全部连接，并返回新的头节点。不允许创建新的链表节点。

提示（原文完整继承）

1. 在纸上画出三个相连的节点，以及 prev 和 cur 两个指针；
2. 在修改 cur.next 之前，先把原来的下一个节点保存到 nxt；
3. 反转 cur.next 后，执行 prev = cur、cur = nxt，然后对原链表的下一个节点重复同样操作。

结合仓库的解法说明

题目「不得创建新节点」意味着只能原地改指针——这正是练习二中「改两条指针、且顺序不能错」思想的强化版。结合 linked_list.py 中 ListNode 的结构（val + next），参考实现如下：

def reverse_linked_list(head: ListNode | None) -> ListNode | None:
    """迭代反转单链表并返回新的头节点"""
    prev: ListNode | None = None
    cur: ListNode | None = head
    while cur:
        nxt = cur.next   # 提示 2：先保存 cur 的原后继，否则断开后丢失
        cur.next = prev  # 反转当前连接
        prev = cur       # 提示 3：双指针整体前移
        cur = nxt
    return prev           # 原头节点已变为尾节点，prev 才是新头

逐步理解（以 1 → 2 → 3 为例）：

轮次	循环前状态	nxt	操作后连接
1	prev = None，cur = 1	2	None ← 1，prev = 1，cur = 2
2	cur = 2	3	1 ← 2，prev = 2，cur = 3
3	cur = 3	None	2 ← 3，prev = 3，cur = None

循环结束时 prev 指向原尾节点 3，它即是新头，链表变为 3 → 2 → 1 → None。

与本章既有代码的呼应值得强调：insert 函数里「先用 n1 缓存旧后继、再改写指针」的保命手法，在这里被推广成循环不变量——每一轮都必须先执行 nxt = cur.next，否则 cur.next = prev 会切断通向链表后半段的路，整条链从 cur 之后丢失，这正是练习二答案第 2 小问「先重写连接会丢失节点 C」的循环放大版。反转完成后，可复用 list_node.py 中的 linked_list_to_list 把新链表序列化为普通列表验证结果。

六、本章练习小结

练习主题	核心结论	源码参照
按位置访问	数组 $O(1)$ 直达；链表需从头沿 next 走 $k-1$ 步，最坏 $O(n)$	linked_list.py
插入元素	数组要逆序搬移元素（$O(n)$）；链表在已知位置处改两条指针（$O(1)$），顺序必须是「先接后继、再挂前驱」	linked_list.py、array.py
动态扩容	底层数组不变长；扩容 = 新建 2 倍容量数组 + 复制全部旧元素 + 换引用	my_list.py
编程题 1（大数加一）	逆序遍历模拟竖式进位，全 9 时头部补 1	手法同 array.py 的逆序循环
编程题 2（反转链表）	三指针 prev / cur / nxt 迭代反转，禁止新建节点	节点结构见 list_node.py

本章节其余页面可继续延伸阅读：array.md（数组）、linked_list.md（链表）、list.md（抽象列表接口）、ram_and_cache.md（内存与缓存），以及同目录下的 summary.md 章节总结。