跳轉至
紙質書（簡體中文版）已發行，詳情請見這裡

# 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 題目解析

##### 歡迎在評論區留下你的見解、問題或建議