解題說明
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()方法來反轉鏈結串列？ - 此實作中有記憶體洩漏的風險嗎？如何改善（如使用智慧指標）？