《Hello 算法》数组与链表章节习题精解概念辨析、复杂度推导与实战编程【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo导读《Hello 算法》的「数组与链表」是全书数据结构的开篇基石。本文基于en/docs/chapter_array_and_linkedlist/exercises.md数组与链表章节练习系统拆解其 3 组概念问答题与 2 道编程实战题并结合仓库中 array.py、linked_list.py、my_list.py 等源码逐题验证结论。读完本文你将能独立推导按位置访问 / 中间插入 / 容量扩容在数组与链表两种存储形态下的真实复杂度并掌握数组存大整数加一与迭代反转单链表两类经典题目的标准解法与边界处理。一、习题定位与知识地图本练习文件是章节 index.md 中「数组与链表」知识的输出型检验配套的正文章节依次为array.md数组的连续内存存储、随机访问、插入删除等基本操作linked_list.md单链表 / 循环链表 / 双向链表的引用式存储与节点操作list.md基于动态数组的列表list及其扩容机制summary.md全章要点回顾与 QA。练习分两个板块概念回顾3 组问答覆盖查找元素 / 插入元素 / 容量增长三个对比维度与编程练习2 道经典算法题。下文先逐题给出分析与答案再进入源码验证与代码实现。二、概念回顾一数组与链表如何按位置找元素题干还原数组与单链表都按序存储[A, B, C, D, E]现在需要访问第 4 个元素D。问题 1数组应使用哪个下标直接访问数组采用从 0 开始的下标体系第 4 个元素对应下标3即arr[3]。下标与元素之间是起始地址 元素大小 × 下标的线性映射关系见 summary.md 中总结的地址公式元素地址 数组起始地址首元素地址 元素大小 × 元素下标这也解释了为什么数组要求元素同类型——只有元素尺寸统一上式中的元素大小才是常数偏移量才可计算。问题 2从A出发单链表依次访问哪些节点链表没有下标只能沿next引用逐个跳跃访问路径为A → B → C → D共移动next指针 3 次。问题 3目标越靠后步数如何变化哪种结构更适合反复按位置访问数组无论下标多大都可由起始地址直接换算得到目标地址按位置访问的时间复杂度恒为 $O(1)$。单链表要访问第 $k$ 个节点必须从头开始走 $k-1$ 次next最坏情况下为$O(n)$。因此反复按位置下标访问的场景下数组全面占优。需要注意这一比较只针对按位置访问并不代表链表在所有操作上都更慢——在插入、删除等改引用操作上链表反而有优势见下一节这正是两种结构优缺点互补的体现。源码印证仓库实现与上述结论严格一致。数组的按址直达能力体现在 array.py 的random_access()中它通过random.randint(0, len(nums) - 1)生成随机下标后直接nums[random_index]返回全程不依赖遍历链表的逐跳访问体现在 linked_list.py 的access(head, index)for _ in range(index): head head.next从头节点走index步才返回目标节点若中途遇到空指针则返回None——这就是 $O(n)$ 的来源。三、概念回顾二数组与链表如何插入元素题干还原数组与单链表都存有A, B, C, D要求在B之后插入X。数组容量为 5当前[A, B, C, D, _]链表为A → B → C → D且你已持有节点B的引用。问题 1数组需要移动哪些元素插入后数组什么样插入点在B下标 1之后即新元素落在下标 2。数组必须从尾部开始依次后移先把D右移一位到下标 4再把C右移一位到下标 3最后把X放入下标 2得到[A, B, X, C, D]插入或删除发生在头部/中部时需要移动 $O(n)$ 个元素这是数组的主要短板。源码印证见 array.py 的insert()其循环正是从最后一个有效位置开始向前遍历、逐个把元素复制到后一位def insert(nums: list[int], num: int, index: int): # 将 index 及其之后的元素全部后移一位 for i in range(len(nums) - 1, index, -1): nums[i] nums[i - 1] nums[index] num问题 2链表应按什么顺序更新X.next与B.next插入后链表什么样B.next原本指向C。正确顺序是先令X.next B.next让X指向C再令B.next X。得到A → B → X → C → D关键陷阱若先执行B.next X覆盖原链接、又不先保存原值节点C就会从链表上失联不可达造成数据丢失。必须先让新节点接上后继再断开旧链接。源码印证linked_list.py 的insert()与上述两步顺序一字不差def insert(n0: ListNode, P: ListNode): n1 n0.next # 先记住后继节点 C P.next n1 # ① P 指向 C n0.next P # ② B 指向 P同理remove()删除n0的后继时也先取P n0.next、n1 P.next再执行n0.next n1让前驱直接跳过被删节点。问题 3为什么必须强调已持有节点B的引用因为链表的 $O(1)$ 插入优势成立的前提是插入位置已知只要知道B的位置插入只改动两个next引用耗时与链表长度无关为 $O(1)$。若题目并未给出B必须先从头节点查找B单是这一趟查找就可能消耗 $O(n)$插入总代价也随之退化为 $O(n)$。这一细节在工程与面试中反复出现链表的$O(1)$ 插入指的是改链接本身而不是定位。四、概念回顾三列表的容量如何增长题干还原一个基于数组的列表当前存有[A, B, C]size 3、capacity 4容量不足时新建一个容量为原容量 2 倍的新数组。问题 1追加D后长度与容量各是多少需要扩容吗D恰好放入最后一个空位内容变为[A, B, C, D]此时size 4、capacity 4不需要扩容。判断是否扩容的条件是追加前size capacity若成立才触发扩容。问题 2再追加E时容量变成多少需要拷贝多少元素此时已无空位系统创建容量为 8 的新数组先把 4 个既有元素A, B, C, D全部拷贝进新数组再写入E最终size 5、capacity 8。问题 3底层数组长度本不可变为何列表容量看起来能增长原数组本身并没有变大。列表的做法是创建一个更大的新数组 → 把既有元素逐个拷贝进去 → 让新数组取代旧数组成为底层存储。从使用者的视角看容量增长发生了但每次扩容都伴随一次 $O(n)$ 的元素搬迁因此 summary.md 明确指出在尾部追加元素并非总是 $O(1)$——一旦触发扩容当次操作退化为 $O(n)$整体看是均摊 $O(1)$。这也解释了列表为何通常以倍数扩容如 $\times 1.5$ 或 $\times 2$扩容次数少、摊薄成本代价是尾部常有无法填满的空闲位造成空间浪费。源码印证仓库在 list.md 的 List Implementation 一节完整演示了这种手写列表对应源码 my_list.py其三个关键设计正是初始容量self._capacity 10长度追踪self._size 0增删时实时更新用于定位列表末尾并判断是否扩容扩容机制self._extend_ratio 2每次翻倍。核心逻辑在add()与extend_capacity()中def add(self, num: int): # 元素个数超出容量时触发扩容机制 if self.size() self.capacity(): self.extend_capacity() self._arr[self._size] num self._size 1 def extend_capacity(self): # 新数组长度为原数组的 _extend_ratio 倍并拷贝原数组 self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) self._capacity len(self._arr)extend_capacity()里原数组 零填充的新增区段本质就是新建大数组并拷贝全部旧元素的等价写法拷贝量等于扩容前的size——与练习第 2 问中拷贝 4 个既有元素完全对应。驱动代码nums MyList()后连续执行 5 次add()第 5 次容量满再循环add(i)共 10 次即可实测容量从 10 翻到 20 时size与capacity的变化。五、编程练习一用数组存储的大整数加一题目描述数组digits从左到右存储一个非负整数的十进制各位例如[3, 0, 8]表示整数 308数字 0 表示为[0]其余输入首位不为 0。请模拟十进制逐位列加法为该整数加 1 并以同格式返回结果。允许直接修改digits若最高位产生新的进位可返回更长的数组。该题即经典的 Plus One 类型题目原文档以外部链接形式给出出处本文不再附链接仅给出完整解法分析。思路推演列竖式加 1 时进位只会从**最低位数组末尾**向高位传播且一旦某一位加后不再产生进位更高位就不会再变化。由此得到三段式算法与原文档 Hints 一一对应从数组最后一个元素开始从右向左扫描如同普通列式加法当前位小于 9该位直接加 1 并立即返回更高位不动当前位等于 9该位变为 0 并继续向左进位若每一位都是 9如[9, 9, 9]全部变为 0 后在数组最前面补一个 1。def plus_one(digits: list[int]) - list[int]: for i in range(len(digits) - 1, -1, -1): if digits[i] 9: digits[i] 1 # 无连续进位直接加一返回 return digits digits[i] 0 # 本位为 9进位后置 0继续向左 return [1] digits # 全部为 9如 [9,9,9]头部补 1正确性与复杂度分析边界情况 ①[0] → [1]不进位边界情况 ②[3, 0, 8] → [3, 0, 9]最低位加一即结束边界情况 ③[1, 2, 9] → [1, 3, 0]产生一次进位边界情况 ④[9, 9, 9] → [1, 0, 0, 0]进位贯穿全部位数组变长长度由 n 变为 n1。时间复杂度为 $O(n)$最坏需从尾走到头一次空间复杂度 $O(1)$不构造辅助数组仅在全部为 9 时才新建长度 1 的结果属于题设允许的返回更长数组。与本章知识的关联该题正是对数组下标即可 $O(1)$ 访问这一特性的直接应用我们通过digits[i]从末位向前随机访问每一位同时利用连续内存、长度固定、从尾部逐步写入的特点完成就地修改无需引入任何链表式节点操作。六、编程练习二迭代反转单链表题目描述给定单链表头节点head每个节点含一个值和一个指向下一节点的next引用请用迭代法反转所有节点间的链接并返回新的头节点不得新建任何链表节点就地反转。思路推演把链表想象成若干箭头反转即把所有next的指向调头。用两个游标prev已反转部分的首端与cur当前待处理节点逐节点推进对应原文档 Hints先在纸上画出三个相连节点及指针prev、cur理清谁指向谁在改写cur.next之前先把原后继保存到nxt否则原链表后半段将丢失执行cur.next prev完成当前节点的转向随后prev cur、cur nxt沿原链表方向继续处理下一节点。def reverse_linked_list(head): prev None # 已反转部分的新头初始为空 cur head # 当前待处理节点 while cur is not None: nxt cur.next # ① 先保存原后继避免断链 cur.next prev # ② 反转当前指针方向 prev cur # ③ prev 前移 cur nxt # ④ cur 沿原链表前移 return prev # 原链表的尾节点即新链表的头示例A → B → C → D反转后为D → C → B → A函数返回原尾节点D。复杂度与边界时间 $O(n)$每个节点恰好被处理一次空间 $O(1)$只用了prev / cur / nxt三个指针变量不新建节点满足题目不得新建链表节点的约束。空链表head is None或单节点链表循环体不执行或只执行一轮直接返回prev天然正确。与本章知识的关联反转过程充分体现了链表通过修改引用改变逻辑结构的本质数据在内存中的位置从未移动变动的只是每个节点next的指向。这也再次呼应了正文 linked_list.md 的核心论断——链表的插入、删除、反转都依赖引用操作而其代价是节点定位必须从头遍历$O(n)$。七、实践与验证在仓库中亲手运行仓库将章节配套代码按语言组织Python 版本位于 en/codes/python/chapter_array_and_linkedlist/与本文概念题直接对应的可运行文件有三个array.py驱动代码演示随机访问、按长度扩展、插入、删除、查找index循环逻辑与链表查找均可对照观察linked_list.py驱动代码初始化1 → 3 → 2 → 5 → 4后依次执行insert(n0, p)、remove(n0)、access(n0, 3)、find(n0, 2)可直接观察两步插入后打印的链表形态my_list.py驱动代码输出容量与长度的实时变化并在第 6 次追加时触发扩容翻倍。在已安装 Python 3 的环境中可用如下命令运行任一文件观察输出python3 codes/python/chapter_array_and_linkedlist/array.py python3 codes/python/chapter_array_and_linkedlist/linked_list.py python3 codes/python/chapter_array_and_linkedlist/my_list.py运行my_list.py时重点观察capacity与size的打印值追加到size capacity 10后再add()一次扩容立即把容量提升到 20——这就是列表容量增长在真实代码中的表现。若需验证数组插入需整体后移的细节可临时给array.py的insert()加打印语句观察后移循环的遍历顺序注意仓库为只读若要修改需先自行拷贝文件不建议改动原仓库文件。八、复习自检清单阅读并完成上述练习后可对照以下清单自查本章掌握度能否用一句话说明数组随机访问 $O(1)$的地址换算原理为什么数组元素必须同类型能否讲清链表插入先接后继、再断前链的顺序以及不保存原后继会引发什么后果能否解释链表的 $O(1)$ 插入为何依赖插入位置已知这一前提能否说明列表扩容的完整三步流程以及为什么尾部追加并不总是 $O(1)$能否在不看答案的情况下独立写出大整数加一与迭代反转链表的代码及其边界用例若个别概念仍有疑问可回到 array.md、linked_list.md、list.md 三篇正文补课并通过 summary.md 的 QA 区解决列表容量扩容为什么 $O(n)$删除节点后要不要把P.next置空等高阶疑问。练习文件中按位置访问、插入次序、容量翻倍这三组概念正是后续章节队列、栈、哈希表、堆等反复使用的基础分析范式值得逐字吃透。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 《Hello 算法》数组与链表章节习题精解：概念辨析、复杂度推导与实战编程
《Hello 算法》数组与链表章节习题精解概念辨析、复杂度推导与实战编程【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo导读《Hello 算法》的「数组与链表」是全书数据结构的开篇基石。本文基于en/docs/chapter_array_and_linkedlist/exercises.md数组与链表章节练习系统拆解其 3 组概念问答题与 2 道编程实战题并结合仓库中 array.py、linked_list.py、my_list.py 等源码逐题验证结论。读完本文你将能独立推导按位置访问 / 中间插入 / 容量扩容在数组与链表两种存储形态下的真实复杂度并掌握数组存大整数加一与迭代反转单链表两类经典题目的标准解法与边界处理。一、习题定位与知识地图本练习文件是章节 index.md 中「数组与链表」知识的输出型检验配套的正文章节依次为array.md数组的连续内存存储、随机访问、插入删除等基本操作linked_list.md单链表 / 循环链表 / 双向链表的引用式存储与节点操作list.md基于动态数组的列表list及其扩容机制summary.md全章要点回顾与 QA。练习分两个板块概念回顾3 组问答覆盖查找元素 / 插入元素 / 容量增长三个对比维度与编程练习2 道经典算法题。下文先逐题给出分析与答案再进入源码验证与代码实现。二、概念回顾一数组与链表如何按位置找元素题干还原数组与单链表都按序存储[A, B, C, D, E]现在需要访问第 4 个元素D。问题 1数组应使用哪个下标直接访问数组采用从 0 开始的下标体系第 4 个元素对应下标3即arr[3]。下标与元素之间是起始地址 元素大小 × 下标的线性映射关系见 summary.md 中总结的地址公式元素地址 数组起始地址首元素地址 元素大小 × 元素下标这也解释了为什么数组要求元素同类型——只有元素尺寸统一上式中的元素大小才是常数偏移量才可计算。问题 2从A出发单链表依次访问哪些节点链表没有下标只能沿next引用逐个跳跃访问路径为A → B → C → D共移动next指针 3 次。问题 3目标越靠后步数如何变化哪种结构更适合反复按位置访问数组无论下标多大都可由起始地址直接换算得到目标地址按位置访问的时间复杂度恒为 $O(1)$。单链表要访问第 $k$ 个节点必须从头开始走 $k-1$ 次next最坏情况下为$O(n)$。因此反复按位置下标访问的场景下数组全面占优。需要注意这一比较只针对按位置访问并不代表链表在所有操作上都更慢——在插入、删除等改引用操作上链表反而有优势见下一节这正是两种结构优缺点互补的体现。源码印证仓库实现与上述结论严格一致。数组的按址直达能力体现在 array.py 的random_access()中它通过random.randint(0, len(nums) - 1)生成随机下标后直接nums[random_index]返回全程不依赖遍历链表的逐跳访问体现在 linked_list.py 的access(head, index)for _ in range(index): head head.next从头节点走index步才返回目标节点若中途遇到空指针则返回None——这就是 $O(n)$ 的来源。三、概念回顾二数组与链表如何插入元素题干还原数组与单链表都存有A, B, C, D要求在B之后插入X。数组容量为 5当前[A, B, C, D, _]链表为A → B → C → D且你已持有节点B的引用。问题 1数组需要移动哪些元素插入后数组什么样插入点在B下标 1之后即新元素落在下标 2。数组必须从尾部开始依次后移先把D右移一位到下标 4再把C右移一位到下标 3最后把X放入下标 2得到[A, B, X, C, D]插入或删除发生在头部/中部时需要移动 $O(n)$ 个元素这是数组的主要短板。源码印证见 array.py 的insert()其循环正是从最后一个有效位置开始向前遍历、逐个把元素复制到后一位def insert(nums: list[int], num: int, index: int): # 将 index 及其之后的元素全部后移一位 for i in range(len(nums) - 1, index, -1): nums[i] nums[i - 1] nums[index] num问题 2链表应按什么顺序更新X.next与B.next插入后链表什么样B.next原本指向C。正确顺序是先令X.next B.next让X指向C再令B.next X。得到A → B → X → C → D关键陷阱若先执行B.next X覆盖原链接、又不先保存原值节点C就会从链表上失联不可达造成数据丢失。必须先让新节点接上后继再断开旧链接。源码印证linked_list.py 的insert()与上述两步顺序一字不差def insert(n0: ListNode, P: ListNode): n1 n0.next # 先记住后继节点 C P.next n1 # ① P 指向 C n0.next P # ② B 指向 P同理remove()删除n0的后继时也先取P n0.next、n1 P.next再执行n0.next n1让前驱直接跳过被删节点。问题 3为什么必须强调已持有节点B的引用因为链表的 $O(1)$ 插入优势成立的前提是插入位置已知只要知道B的位置插入只改动两个next引用耗时与链表长度无关为 $O(1)$。若题目并未给出B必须先从头节点查找B单是这一趟查找就可能消耗 $O(n)$插入总代价也随之退化为 $O(n)$。这一细节在工程与面试中反复出现链表的$O(1)$ 插入指的是改链接本身而不是定位。四、概念回顾三列表的容量如何增长题干还原一个基于数组的列表当前存有[A, B, C]size 3、capacity 4容量不足时新建一个容量为原容量 2 倍的新数组。问题 1追加D后长度与容量各是多少需要扩容吗D恰好放入最后一个空位内容变为[A, B, C, D]此时size 4、capacity 4不需要扩容。判断是否扩容的条件是追加前size capacity若成立才触发扩容。问题 2再追加E时容量变成多少需要拷贝多少元素此时已无空位系统创建容量为 8 的新数组先把 4 个既有元素A, B, C, D全部拷贝进新数组再写入E最终size 5、capacity 8。问题 3底层数组长度本不可变为何列表容量看起来能增长原数组本身并没有变大。列表的做法是创建一个更大的新数组 → 把既有元素逐个拷贝进去 → 让新数组取代旧数组成为底层存储。从使用者的视角看容量增长发生了但每次扩容都伴随一次 $O(n)$ 的元素搬迁因此 summary.md 明确指出在尾部追加元素并非总是 $O(1)$——一旦触发扩容当次操作退化为 $O(n)$整体看是均摊 $O(1)$。这也解释了列表为何通常以倍数扩容如 $\times 1.5$ 或 $\times 2$扩容次数少、摊薄成本代价是尾部常有无法填满的空闲位造成空间浪费。源码印证仓库在 list.md 的 List Implementation 一节完整演示了这种手写列表对应源码 my_list.py其三个关键设计正是初始容量self._capacity 10长度追踪self._size 0增删时实时更新用于定位列表末尾并判断是否扩容扩容机制self._extend_ratio 2每次翻倍。核心逻辑在add()与extend_capacity()中def add(self, num: int): # 元素个数超出容量时触发扩容机制 if self.size() self.capacity(): self.extend_capacity() self._arr[self._size] num self._size 1 def extend_capacity(self): # 新数组长度为原数组的 _extend_ratio 倍并拷贝原数组 self._arr self._arr [0] * self.capacity() * (self._extend_ratio - 1) self._capacity len(self._arr)extend_capacity()里原数组 零填充的新增区段本质就是新建大数组并拷贝全部旧元素的等价写法拷贝量等于扩容前的size——与练习第 2 问中拷贝 4 个既有元素完全对应。驱动代码nums MyList()后连续执行 5 次add()第 5 次容量满再循环add(i)共 10 次即可实测容量从 10 翻到 20 时size与capacity的变化。五、编程练习一用数组存储的大整数加一题目描述数组digits从左到右存储一个非负整数的十进制各位例如[3, 0, 8]表示整数 308数字 0 表示为[0]其余输入首位不为 0。请模拟十进制逐位列加法为该整数加 1 并以同格式返回结果。允许直接修改digits若最高位产生新的进位可返回更长的数组。该题即经典的 Plus One 类型题目原文档以外部链接形式给出出处本文不再附链接仅给出完整解法分析。思路推演列竖式加 1 时进位只会从**最低位数组末尾**向高位传播且一旦某一位加后不再产生进位更高位就不会再变化。由此得到三段式算法与原文档 Hints 一一对应从数组最后一个元素开始从右向左扫描如同普通列式加法当前位小于 9该位直接加 1 并立即返回更高位不动当前位等于 9该位变为 0 并继续向左进位若每一位都是 9如[9, 9, 9]全部变为 0 后在数组最前面补一个 1。def plus_one(digits: list[int]) - list[int]: for i in range(len(digits) - 1, -1, -1): if digits[i] 9: digits[i] 1 # 无连续进位直接加一返回 return digits digits[i] 0 # 本位为 9进位后置 0继续向左 return [1] digits # 全部为 9如 [9,9,9]头部补 1正确性与复杂度分析边界情况 ①[0] → [1]不进位边界情况 ②[3, 0, 8] → [3, 0, 9]最低位加一即结束边界情况 ③[1, 2, 9] → [1, 3, 0]产生一次进位边界情况 ④[9, 9, 9] → [1, 0, 0, 0]进位贯穿全部位数组变长长度由 n 变为 n1。时间复杂度为 $O(n)$最坏需从尾走到头一次空间复杂度 $O(1)$不构造辅助数组仅在全部为 9 时才新建长度 1 的结果属于题设允许的返回更长数组。与本章知识的关联该题正是对数组下标即可 $O(1)$ 访问这一特性的直接应用我们通过digits[i]从末位向前随机访问每一位同时利用连续内存、长度固定、从尾部逐步写入的特点完成就地修改无需引入任何链表式节点操作。六、编程练习二迭代反转单链表题目描述给定单链表头节点head每个节点含一个值和一个指向下一节点的next引用请用迭代法反转所有节点间的链接并返回新的头节点不得新建任何链表节点就地反转。思路推演把链表想象成若干箭头反转即把所有next的指向调头。用两个游标prev已反转部分的首端与cur当前待处理节点逐节点推进对应原文档 Hints先在纸上画出三个相连节点及指针prev、cur理清谁指向谁在改写cur.next之前先把原后继保存到nxt否则原链表后半段将丢失执行cur.next prev完成当前节点的转向随后prev cur、cur nxt沿原链表方向继续处理下一节点。def reverse_linked_list(head): prev None # 已反转部分的新头初始为空 cur head # 当前待处理节点 while cur is not None: nxt cur.next # ① 先保存原后继避免断链 cur.next prev # ② 反转当前指针方向 prev cur # ③ prev 前移 cur nxt # ④ cur 沿原链表前移 return prev # 原链表的尾节点即新链表的头示例A → B → C → D反转后为D → C → B → A函数返回原尾节点D。复杂度与边界时间 $O(n)$每个节点恰好被处理一次空间 $O(1)$只用了prev / cur / nxt三个指针变量不新建节点满足题目不得新建链表节点的约束。空链表head is None或单节点链表循环体不执行或只执行一轮直接返回prev天然正确。与本章知识的关联反转过程充分体现了链表通过修改引用改变逻辑结构的本质数据在内存中的位置从未移动变动的只是每个节点next的指向。这也再次呼应了正文 linked_list.md 的核心论断——链表的插入、删除、反转都依赖引用操作而其代价是节点定位必须从头遍历$O(n)$。七、实践与验证在仓库中亲手运行仓库将章节配套代码按语言组织Python 版本位于 en/codes/python/chapter_array_and_linkedlist/与本文概念题直接对应的可运行文件有三个array.py驱动代码演示随机访问、按长度扩展、插入、删除、查找index循环逻辑与链表查找均可对照观察linked_list.py驱动代码初始化1 → 3 → 2 → 5 → 4后依次执行insert(n0, p)、remove(n0)、access(n0, 3)、find(n0, 2)可直接观察两步插入后打印的链表形态my_list.py驱动代码输出容量与长度的实时变化并在第 6 次追加时触发扩容翻倍。在已安装 Python 3 的环境中可用如下命令运行任一文件观察输出python3 codes/python/chapter_array_and_linkedlist/array.py python3 codes/python/chapter_array_and_linkedlist/linked_list.py python3 codes/python/chapter_array_and_linkedlist/my_list.py运行my_list.py时重点观察capacity与size的打印值追加到size capacity 10后再add()一次扩容立即把容量提升到 20——这就是列表容量增长在真实代码中的表现。若需验证数组插入需整体后移的细节可临时给array.py的insert()加打印语句观察后移循环的遍历顺序注意仓库为只读若要修改需先自行拷贝文件不建议改动原仓库文件。八、复习自检清单阅读并完成上述练习后可对照以下清单自查本章掌握度能否用一句话说明数组随机访问 $O(1)$的地址换算原理为什么数组元素必须同类型能否讲清链表插入先接后继、再断前链的顺序以及不保存原后继会引发什么后果能否解释链表的 $O(1)$ 插入为何依赖插入位置已知这一前提能否说明列表扩容的完整三步流程以及为什么尾部追加并不总是 $O(1)$能否在不看答案的情况下独立写出大整数加一与迭代反转链表的代码及其边界用例若个别概念仍有疑问可回到 array.md、linked_list.md、list.md 三篇正文补课并通过 summary.md 的 QA 区解决列表容量扩容为什么 $O(n)$删除节点后要不要把P.next置空等高阶疑问。练习文件中按位置访问、插入次序、容量翻倍这三组概念正是后续章节队列、栈、哈希表、堆等反复使用的基础分析范式值得逐字吃透。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考