解題說明
Design Linked List
題目描述:設計一個鏈結串列的實作,支援以下操作:get(index) 取得第 index 個節點的值、addAtHead(val) 在頭部新增節點、addAtTail(val) 在尾部新增節點、addAtIndex(index, val) 在指定位置插入節點、deleteAtIndex(index) 刪除指定位置的節點。
解題思路:使用帶有 dummy head(虛擬頭節點)的單向鏈結串列,加上一個 size 變數追蹤長度。dummy head 簡化了邊界條件的處理(不需要特別處理空串列或在頭部插入的情況):
- get:從 dummy head 開始走 index+1 步。
- addAtHead:在 dummy head 後面插入新節點。
- addAtTail:走到尾端插入。
- addAtIndex:走到第 index 個節點的前一個,插入新節點。
- deleteAtIndex:走到第 index 個節點的前一個,跳過目標節點。
C++ 解法
複雜度分析
時間複雜度:get、addAtIndex、deleteAtIndex 為 O(n)(需要遍歷到指定位置);addAtHead 為 O(1);addAtTail 為 O(n)(若不額外維護尾指標)。
空間複雜度:O(n) — 存放 n 個節點。
虛擬碼
1. Initialize dummy head node, size = 0 2. get(index): walk index+1 steps from dummy, return val or -1 3. addAtHead(val): insert new node after dummy 4. addAtTail(val): walk to end, append new node 5. addAtIndex(index, val): walk to position index (from dummy), insert after prev 6. deleteAtIndex(index): walk to position index, skip target node
其他解法
雙向鏈結串列:加上 prev 指標和 dummy tail,可以讓 addAtTail 和從尾端操作都變成 O(1)。空間多一個指標/節點,但大幅改善尾端操作效能。
用陣列模擬:用 vector 實作,get 為 O(1),但插入和刪除為 O(n)(需要移動元素)。適合讀取頻繁、修改較少的場景。
延伸思考
- 如何修改為雙向鏈結串列以優化 addAtTail 到 O(1)?
- 如何加上
reverse()方法來反轉鏈結串列? - 此實作中有記憶體洩漏的風險嗎?如何改善(如使用智慧指標)?