一、鏈表的基本結構 鏈表是由節點和指針構成的數據結構，每個節點存有一個值，和一個指向下一個節點的指針。不同於數組，鏈表並不能隨機訪問，必須透過指針找到該節點才能獲取其值；同理在未遍歷到鏈表結尾時，我們也無法知道鏈表長度，除非依賴其它數據結構儲存長度。 LeetCode 中默認的鏈表： struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; 二、鏈表的基本操作 在開始演算法實踐前，先來練習一下鏈表的 CRUD 吧！ 1. 查(Read) 由於鏈表並非在儲存格中連續分布，所以無法用索引進行隨機訪問，所以我們必須逐個訪問，直到到達我們想要的元素。 藉由指針每次指向當前節點的 next，移動 n 次到達 index 為 n 的節點。 int at(ListNode* head, int n){ // index 為 n ListNode* curr = head; while (n--){ // 移動 n 次 curr = curr->next; } return curr->val; } 2. 改(Update) 改的步驟，只是將查完的元素予以賦值。 void update(ListNode* head, int n, int val){ ListNode* curr = head; while (n--){ curr = curr->next; } curr->val = val; // 查完後賦值 } 3. 增(create) 如果要新增節點，則必須找到要插入位置的前一個節點。 ListNode* insert(ListNode* head, int n, int val){ if (!head) return NULL; // 處理當鏈表為空的狀態 if (n == 0){ // 處理當插入位置為 0 時的特例 ListNode* newHead = new ListNode(val, head); head = newHead; return head; } ListNode* curr = head; while (curr && --n){ // 移動到插入位置的前一位 curr = curr->next; } ListNode* tmp = curr->next; // 預先存下來插入位置的後一位 curr->next = new ListNode(val); // 插入元素 curr->next->next = tmp; // 將元素的下一位指派給存下來的後一位 return head; } 上述的寫法很直觀，但需要處例首位的特例，不夠漂亮，這時我們常會用到 DUMMY HEAD 的手法，即在鏈表最開頭先創一個假的節點，最後再返回該節點的下一位。 ListNode* insert(ListNode* head, int n, int val){ if (!head) return NULL; ListNode* dummy = new ListNode(-1, head); // 創建一個 dummy head ListNode* curr = dummy; while (curr && n--){ // 注意為 n-- curr = curr->next; } ListNode* tmp = curr->next; curr->next = new ListNode(val); curr->next->next = tmp; return dummy->next; // 注意為返回 dummy 的下一位 } 前面兩解都是在可以取得前一位，且不更改節點的值的前提下的解法。如果只能取得當下的節點，則可以使用增+更的手法。 void insert(ListNode* node, int val){ int tmp = node->val; node->val = val; node->next = new ListNode(tmp, node->next); } 4. 減(delete) 與增類似，取得前一位再利用更改指針的方式達到刪除。 ListNode* erase(ListNode* head, int n, int val){ if (!head) return NULL; ListNode* dummy = new ListNode(-1, head); ListNode* curr = dummy; while (curr && n--){ curr = curr->next; } curr->next = curr->next->next; // 將前一位的後一位指給後一位 return dummy->next; } 只能取得當下節點的作法： [LeetCode. 237] Delete Node in a Linked List(Medium) void insert(ListNode* node, int val){ node->val = node->next->val; // 將當前的值賦值成下一位的值 node->next = node->next->next; // 將下一個節點刪除 } 三、鏈表的進階操作 1. 刪值 如何刪除表中第一個出現指定值的節點，同樣找到該值的前一個節點，再使用刪除的手法即可： void remove(ListNode* head, int target){ ListNode* prev = NULL; ListNode* curr = head; while (curr && curr->val != target){ prev = curr; curr = curr->next; } if (!prev) // 處理例外 head = head->next; else prev->next = prev->next->next; } 2. 建表 如何藉由一個數組建立一鏈表，可以藉由前面使用的 dummy head 的手法： ListNode* build(vector<int> nums){ ListNode* dummy = new ListNode(-1); ListNode* prev = dummy; ListNode* curr = NULL; for (int i = 0; i < nums.size(); i++){ curr = new ListNode(nums[i]); prev->next = curr; prev = curr; curr = curr->next; } ListNode* head = dummy->next; delete(dummy); return head; } 3. 鏈表的後序遍歷 前文說過，鏈表也可以做前序與後序的遍歷，在此我們再複習一次。 void traverse(ListNode* head){ // pre-order traverse(head->next); // post-order } 如果我們想移除鏈表中所有值等於 target 的節點，用迭代的作法為： void removeAll(ListNode* head, int target){ ListNode* dummy = new ListNode(-1, head); ListNode* curr = dummy; while (curr && curr->next){ if (curr->next->val == target){ // 當前節點的下一位符合 target 則刪除它 curr->next = curr->next->next; } else { curr = curr->next; // 否則則繼續後下遍歷 } } } 那如果用遞迴的寫法呢： void removeAll(ListNode* head, int target){ if (!head) return; // 假如鏈表為空，則退出函式 while (head && head->val == target){ if (head->next){ head->val = head->next->next; head->next = head->next->next; // 刪除 } else { head = NULL; // 當最後一個元素需移除時 } } removeAll(head->next, target) // 前序遍歷 } 後序跟前序有個很維妙的差別在於：後序遍歷可以將值傳回給前一個元素！ 試試看用後序回傳值的特徵來實作這個函式 void removeAll(ListNode* head, int target){ int tmp; if (head->next) tmp = removeAll(head->next, target) // recursion if (tmp == target) // 後序遍歷可以取得下一位的回傳的值 head->next = head->next->next; // 有了需要刪除的節點的前一位，要刪除就容易啦！ return head->val // 傳回當前節點的值 } 四、秀一波的操作 1. 刪值 用兩個節點去做到鏈表刪除的操作，還是有一點點不夠美，試試看下面這個 pointer to pointer 的解法吧！ 改自文章你所不知道的 C 語言: linked list 和非連續記憶體 void remove(ListNode* head, int target){ ListNode** curr = &head; // 將指向指針的 curr 指向 head while ((*curr)->val != target) curr = &(*curr)->next; if (!(*curr)) return; // 避免掉指向 NULL *curr = (*curr)->next } 2. 建表 學會上面這個 pointer to pointer 的作法，不如試試看來用這個方法來建表！ ListNode* build(vector<int> nums){ ListNode* head = new ListNode(nums[0]); ListNode** curr = &head; for (int i = 0; i < nums.size(); i++){ (*curr)->next = new ListNode(nums[i]); curr = &(*curr)->next; } } 五、鏈表的演算法 1. 反轉鏈表 [LeetCode. 206] Reverse Linked List(Easy) 藉由剛剛學習到鏈表的操作，用迭代的方式來解題吧。 考慮到一個反轉鏈表的連續操作，我們需要有三個節點 prev, curr, next。 ListNode* reverse(ListNode* head){ ListNode* prev = NULL; ListNode* curr = head; ListNode* next = NULL; while (curr){ next = curr->next; // 先記住下一個位置 curr->next = prev; // 將指針指向前一位，以達成反轉的目的 prev = curr; // 往前移動 curr = next; // 往前移垂 } return prev; } 那如果用遞迴的方式寫呢？ ListNode* reverse(ListNode* head){ if (!head || head->next) return head; // 處理終止條件 ListNode last = reverse(head->next); // post-order traversal：回傳已排序好的子鏈表，並傳回最後一項 head->next->next = head; head->next = NULL; return last; } [[Followup] 反轉前 N 個節點 反轉鏈表的前 N 個節點：用前面的函式稍作修改 ListNode* successor = NULL; ListNode* reverseN(ListNode* head, int n){ if (n == 1){ // 只反轉 1 個節點相當於沒有反轉，故轉回自己 successor = head->next; // 記錄反轉後的鏈表要接到哪裡->剩餘鏈表的頭 return head; } ListNode last = reverseN(head->next, n-1); head->next->next = head; head->next = successor; // 最後將鏈表的尾巴接到剩餘鏈表的頭 return last; } [LeetCode. 92] Reverse Linked List II(Medium) 反轉第 m 到第 n 個節點中間的節點 前進 m - 1 次就相當於就相當於反轉前 (n-m-1) 個節點，就可以用 reverseN 解了。 ListNode* reverseBetween(ListNode* head, int m, int n){ if (m == 1){ return reverseN(head, n); // 與 LeetCode.92 一樣 } head->next = reverseBetween(head->next, m-1, n-1); // 前進到 base case return head; } [LeetCode. 25] Reverse Nodes in k-Group (Hard) 結合前面的經驗，注意遞迴該返回的值是什麼。 注意結尾若節數小於 k 則不則 reverse。 ListNode* reverseKGroup(ListNode* head, int k) { ListNode* curr = head; int cnt = 0; while (curr && cnt < k){ curr = curr->next; cnt++; } if (cnt == k){ // 當節數小於 k 時，不做 reverse curr = reverseKGroup(curr, k); // 傳回的是 reverse 完的鏈表的 head，故需把 reverse 完的尾與之相接 while (cnt-- > 0){ ListNode* next = head->next; head->next = curr; curr = head; head = next; } return curr; // 當節數等於 k 時回傳的是尾巴 } return head; // 注意節數小於 k 時仍回傳 head } 2. 環型鏈表(龜兔賽跑-快慢指針) [LeetCode. 141] Linked List Cycle(Easy) 快慢指針是雙指針的一種應用，利用兩個指針移動的速度不同來達到目的。最經典的題型就是找尋鏈表是否含有環。 要檢查鏈表是否有環，可以使用找尋圖(graph)中是否有環的技巧，並利用 visited 來檢查是否有拜訪過，但下面快慢指針的技巧可以不用額外使用空間，使空間複雜度降到 \(O(1)\)。 bool hasCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast && fast->next){ // 確保快指針與他的下一位都不是 NULL fast = fast->next->next; // 快指針走兩步 slow = slow->next; // 慢指針走一步 if (fast == slow) return true; // 若兩者相撞，則必有環 } return false; } [LeetCode. 142] Linked List Cycle II(Medium) 此題是要找尋鏈表中若有環，則相交點是哪一點： 因為快指針走的距離是慢指針 k 的兩倍，令相遇點距相交點距離為 m 圓環的長度為 L：
\(\text{L + m + k = 2 * k}\)
\(\text{L = k - m}\)
故起點到相交點的長度 \(\text{k - m}\) 與相遇點到相交點的長度 \(\text{k - m}\) 相同。 ListNode *detectCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast && fast->next){ fast = fast->next->next; slow = slow->next; if (fast == slow) break; // 若有環則退出 } if (!fast || !fast->next) return NULL; // 若快指針已經走到底表示沒有環 fast = head; // 讓其中一個指針從頭開始走，並一同樣的速度走 while (fast != slow){ // 相遇點即為相交點 fast = fast->next; slow = slow->next; } return fast; } [LeetCode. 876] Middle of the Linked List(Easy) 這題當然可以先遍歷一遍取得鏈表長度後，再重新以長度計量，走一半的長度來得到答案，但很顯然不夠漂亮，用快慢指針，令快指針比慢指針移動速度快兩倍，當快指針走完時，慢指針即指向中點。以此類推可求1/3的節點、2/5的節點等。 ListNode* middleNode(ListNode* head) { ListNode* fast = head; ListNode* slow = head; while (fast && fast->next){ fast = fast->next->next; slow = slow->next; } return slow; } 3. 雙指針(前後指針) [LeetCode. 19] Remove Nth Node From End of List(Medium) 這題也是簡單的雙指針問題，當前指針先走 n 步，兩指針以同樣速度往前走(即前後指針始終保持 n 的距離)，則前指針走完時，後指針指向倒數第 k 個節點。 ListNode* removeNthFromEnd(ListNode* head, int n) { // 注意以下我們要刪除第 n 個節點，故我們需找第 n-1 個節點，為避免刪除第一個節點的例子，我們引入 dummy ListNode* dummy = new ListNode(-1, head); ListNode* slow = dummy; ListNode* fast = dummy; while (fast && n--){ // 前指針先行走 n 個節點 fast = fast->next; } while (fast->next){ // 保持等速 slow = slow->next; fast = fast->next; } slow->next = slow->next->next; // 刪除第 n 個節點 return dummy->next; } [LeetCode. 160] Intersection of Two Linked Lists(Easy) 找兩條鏈表的相交點，這題也可以用雙指針的方式解，當 A 鏈懷走完鏈表立即讓它接回 B 鏈表，B 鏈表亦如是，則相遇點則會是相交點，因為此時它們各別則的距離是都是 A 鏈表的長度加上 B 鏈表的長度，但要注意要記錄是否已經接過一遍，如果沒有相交點，又無限接下去，則程式永遠不會停止。 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* a = headA; ListNode* b = headB; bool flagA = true; // 用來標記是否已接過另一鏈表 bool flagB = true; // 用來標記是否已接過另一鏈表 while (a && b){ if (a == b) return a; // 相遇表示相交點 a = a->next; b = b->next; if (!a && flagA){ a = headB; flagA = false; // 已接過另一鏈表 } if (!b && flagB){ b = headA; flagB = false; // 已接過另一鏈表 } } return NULL; } [LeetCode. 86] Partition List(Medium) 具體作法可將鏈表一分為二，待兩條鏈表皆完成後再頭尾相接。 ListNode* partition(ListNode* head, int x) { ListNode* dummy1 = new ListNode(-1); ListNode* dummy2 = new ListNode(-1); ListNode* curr1 = dummy1; ListNode* curr2 = dummy2; while (head){ if (head->val < x){ curr1->next = head; curr1 = curr1->next; } else { curr2->next = head; curr2 = curr2->next; } head = head->next; } curr1->next = dummy2->next; curr2->next = NULL; return dummy1->next; } [LeetCode. 21] Merge Two Sorted Lists(Easy) 簡單的 if-else，搭配 dummy 的做法即可解題。 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* dummy = new ListNode(-1); ListNode* curr = dummy; while (list1 && list2){ if (list1->val <= list2->val){ curr->next = list1; list1 = list1->next; } else { curr->next = list2; list2 = list2->next; } curr = curr->next; } curr->next = list1 ? list1 : list2; return dummy->next; } 4. 優先佇列 [LeetCode. 23] Merge k Sorted Lists(Hard) 這一題有點 tricky，我們可以用到優先佇列，由於每次比較只會比較鏈表的頭節表，故我們連續將鏈表推至 min heap 上，並每次把 min heap 頂端的節點接到新的鏈表後，再把 min heap 上的鏈表拿去頭後，再丟回優先佇列中，至到鏈表走完，即完成。 ListNode* mergeKLists(vector<ListNode*>& lists) { auto cmp = [](ListNode* a, ListNode* b){return a->val > b->val;}; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp); ListNode* dummy = new ListNode(-1); ListNode* curr = dummy; for (ListNode* node : lists){ if (node) pq.push(node); } while (!pq.empty()){ ListNode* node = pq.top(); pq.pop(); curr->next = node; curr = curr->next; node = node->next; if (node) pq.push(node); } return dummy->next; } 回到目錄：[Algo] 演算法筆記 想要複習：[Algo] 0-2. 演算法思維 接著閱讀：[Algo] 0-4. 二元樹(Binary Tree)
