跳转至

4.6   练习

4.6.1   知识巩固

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)\) 时间。

    这里只比较按位置读取，不表示链表在所有操作上都更慢。

2.   数组和链表怎样插入元素

数组和单向链表中都保存了 A、B、C、D。现在要在 B 后面插入 X：

  • 数组容量为 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)\) 时间。

3.   列表容量是怎样增长的

一个基于数组实现的列表当前内容为 [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 的新数组， 将 A、B、C、D 共 4 个原有元素复制过去，再加入 E。 此时 size = 5、capacity = 8。

  3. 原来的数组本身没有变长。列表创建了一个更大的新数组，复制原有元素， 再改用新数组作为底层存储，因此对使用者来说容量增长了。

4.6.2   编程练习

1.   数组表示的大整数加一

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

请模拟一次十进制竖式加法，将这个整数增加 1，并把结果仍按相同的数组形式返回。 可以直接修改 digits；若最前面产生新的进位，可以返回一个更长的数组。

解题提示
  1. 像做竖式加法一样，从数组最后一位开始
  2. 当前位小于 9 时加一后即可立即返回
  3. 当前位等于 9 时把它改成 0；若所有位都是 9，需要在最前面补 1

LeetCode

2.   反转单向链表

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

请使用迭代方法反转所有节点之间的连接，并返回反转后的头节点。 要求不创建新的链表节点。

解题提示
  1. 先在纸上画出三个相连的节点和 prev、cur 两个指针
  2. 改写 cur.next 前，必须先用 nxt 保存原来的下一个节点
  3. 反转 cur.next 后，令 prev = cur，再令 cur = nxt，继续处理原链表中的下一个节点

LeetCode 题目解析

欢迎在评论区留下你的见解、问题或建议