跳轉至

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

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