目錄

• 題意速覽
• 解題思路與設計要點
• C++ 代碼實現（單鏈表 + 虛擬頭結點）
• 時間復雜度與空間復雜度
• 常見坑位與邊界用例
• 對比：雙鏈表如何優化
• 單元測試樣例（可直接粘貼運行）
• 總結

---

題意速覽

設計一個支持如下操作的鏈表：

• get(index)：返回索引 index 處的值，不合法返回 -1；
• addAtHead(val)：頭插；
• addAtTail(val)：尾插；
• addAtIndex(index, val)：在 index 位置前插入；如果 index==size 等價尾插；如果 index>size 不插；如果 index<0 按頭插處理；
• deleteAtIndex(index)：刪除 index 處節點，非法索引則忽略。

---

解題思路與設計要點

• 使用「虛擬頭結點 DummyHead」簡化邊界：頭插、刪頭都不用特判。
• 維護 size 保證 O(1) 判合法與尾插定位邊界；
• 單鏈表前驅節點訪問需要遍歷，統一封裝「定位到 index 的前一節點」的輔助函數；
• addAtIndex 對 index<0 視為 0（題目要求），對 index>size 直接 return；
• deleteAtIndex 需校驗范圍 [0, size-1]。

---

C++ 代碼實現（單鏈表 + 虛擬頭結點）

#include <bits/stdc++.h>
using namespace std;class MyLinkedList {
public:struct Node {int val; Node* next;Node(int v=0): val(v), next(nullptr) {}};MyLinkedList() {_dummy = new Node(); // 虛擬頭_size = 0;}int get(int index) {if (index < 0 || index >= _size) return -1;Node* cur = _dummy->next;while (index--) cur = cur->next;return cur->val;}void addAtHead(int val) {addAtIndex(0, val);}void addAtTail(int val) {addAtIndex(_size, val);}void addAtIndex(int index, int val) {if (index > _size) return;          // 超界不插if (index < 0) index = 0;           // 負數按 0 處理Node* prev = _dummy;for (int i = 0; i < index; ++i) prev = prev->next;Node* node = new Node(val);node->next = prev->next;prev->next = node;++_size;}void deleteAtIndex(int index) {if (index < 0 || index >= _size) return;Node* prev = _dummy;for (int i = 0; i < index; ++i) prev = prev->next;Node* del = prev->next;prev->next = del->next;delete del;--_size;}~MyLinkedList() {Node* cur = _dummy;while (cur) { Node* nxt = cur->next; delete cur; cur = nxt; }}private:Node* _dummy;int _size;
};

---

時間復雜度與空間復雜度

• get / addAtIndex / deleteAtIndex 定位需要 O(n)；
• addAtHead / addAtTail 退化到 O(n)（單鏈表無尾指針情況下），如需 O(1) 尾插可維護尾指針；
• 額外空間 O(1)（不計存儲本身）。

---

常見坑位與邊界用例

• index == size 允許插入（等價尾插）；index > size 直接忽略。
• index < 0 視為頭插；
• 先移動到前驅位置再插/刪，避免對 index==0 的特判；
• 刪除后別忘 --size，插入后 ++size；
• 析構釋放所有節點（在線評測不強制，但工程上必須）。

推薦用例（覆蓋邊界）：

addAtHead(1)            -> [1]
addAtTail(3)            -> [1,3]
addAtIndex(1,2)         -> [1,2,3]
get(1) == 2
deleteAtIndex(1)        -> [1,3]
get(1) == 3
addAtIndex(5,10)        -> ignore
addAtIndex(-2,7)        -> [7,1,3]

---

對比：雙鏈表如何優化

• 額外存 prev 指針，可 O(1) 從任意節點刪除；
• 若同時維護尾指針與 size，addAtTail 可達 O(1)；
• 但節點更重，內存與指針安全性要求更高（注意野指針/懸垂指針）。

---

單元測試樣例（可直接粘貼運行）

#include <bits/stdc++.h>
using namespace std;// 將上面的 MyLinkedList 粘貼到此處int main() {MyLinkedList list;list.addAtHead(1);list.addAtTail(3);list.addAtIndex(1, 2);   // [1,2,3]cout << list.get(1) << "\n"; // 2list.deleteAtIndex(1);   // [1,3]cout << list.get(1) << "\n"; // 3list.addAtIndex(5, 10);  // ignorelist.addAtIndex(-2, 7);  // [7,1,3]cout << list.get(0) << "," << list.get(1) << "," << list.get(2) << "\n"; // 7,1,3return 0;
}

---

總結

• 這題的本質是「抽象一個受控的鏈表 API」，工程感強：
  • 統一用 Dummy Head 吸收邊界。
  • 明確 index 規則并維護 size。
  • 寫完先過“增刪改查 + 異常輸入”的自測清單。
• 若要進一步提速，可切到雙鏈表并維護尾指針；如對內存敏感或題目簡單，單鏈表足夠。