算法面試套路｜原地反轉鏈表（In-place Reversal of Linked-List）

--- title: "算法面試套路｜原地反轉鏈表（In-place Reversal of Linked-List）" description: "Patterns for Coding Questions: Depth-First Search." image: https://i.imgur.com/Wnnr2qC.png author: Hsins tags: LeetCode, Coding Interview robots: breaks: GA: disqus: --- # 算法面試套路｜原地反轉鏈表（In-place Reversal of Linked-List） <img src="https://i.imgur.com/Wnnr2qC.png" height=200/> > 本篇內容主要為 [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。 ## 重點整理 - 原地反轉鏈表（In-place Reversal of Linked-List） - 策略：使用現有的節點物件實例，而不使用額外的記憶體 - 題型： - 樹的逐層順序遍歷 - 樹的層級相關操作 ## 題目匯總 - `0025` Reverse Linked List II - `0092` Reverse Nodes in k-Group ## [例題] Reverse a Linked-List ### 問題給定一個單向鏈結串列（singly linked-list）的頭節點，反轉此鏈結串列，撰寫一函數返回鏈結串列反轉後的頭節點。 **Example** <img src="https://i.imgur.com/QBiNhuw.png" /> ### 題解為了反轉鏈結串列，我們需要每一次反轉一個節點。我們使用變數 `current` 在一開始指向鏈結串列的頭節點，並用變數 `previous` 指向遍歷過的節點，在最一開始他將指向 `null`。在後續的步驟中，我們透過在向下一個節點前進之前，將當前節點 `current` 指向 `previous` 來反轉當前節點；同時，我們需要更新 `previous` 為剛處理過的節點。上述演算法如圖所示： <img src="https://i.imgur.com/qhkwlsH.png"> <img src="https://i.imgur.com/9DKQqBf.png"> <img src="https://i.imgur.com/FgKmXKU.png"> <img src="https://i.imgur.com/lFGGKdK.png"> <img src="https://i.imgur.com/kf5C57h.png"> <img src="https://i.imgur.com/qibrGQs.png"> <img src="https://i.imgur.com/rwQQ3GX.png"> ### 代碼 #### C++ ``` cpp class ReverseLinkedList { public: static ListNode *reverse(ListNode *head) { ListNode *curr = head; ListNode *prev = nullptr; ListNode *next = nullptr; while (curr != nullptr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } } ``` #### Java ``` java class ReverseLinkedList { public static ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; ListNode next = null; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } } ``` #### JavaScript ``` javascript const reverse = (head) => { let curr = head; let prev = null; let next = null; while (curr !== null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } ``` #### Python ``` python def reverse(head): prev, curr, next = None, head, None while curr is not None: next = curr.next curr.next = prev prev = curr curr = next return prev ``` ### 分析 - 時間複雜度：$\mathcal{O}(n)$，其中 $n$ 為鏈結串列中的節點總數 - 空間複雜度：$\mathcal{O}(1)$ ## [例題] Reverse a Sub-List ### 問題給定一個鏈結串列（singly linked-list）與兩個位置 `p` 和 `q`，反轉鏈結串列中 `p` 至 `q` 之間的部分。 **Example** <img src="https://i.imgur.com/WPVKFra.png" /> ### 題解這一題遵循 **原地反轉鏈表（In-place Reversal of Linked-List）** 策略，我們將使用與 [Reverse a Linked-List](#例題-Reverse-a-Linked-List) 相同的處理方式。步驟如下： 1. 省略前面 `p-1` 個結點，直到抵達位置 `p` 2. 保存第 `p-1` 個結點的位置，用來串起後續反轉部分鏈結串列 3. 使用 [Reverse a Linked-List](#例題-Reverse-a-Linked-List) 的解決方法翻轉 `p` 到 `q` 之間的鏈結串列 4. 將上述翻轉的部分與 `p-1` 和 `q+1` 連結 ### 代碼 #### C++ ``` cpp ``` #### Java ``` java class ReverseSubList { public static ListNode reverse(ListNode head, int p, int q) { if (p == q) return head; // skipping 'p-1' nodes, curr will point to 'p' node ListNode curr = head; ListNode prev = null; for (int i = 0; curr != null && i < p - 1; ++i) { prev = curr; curr = curr.next; } // focus three parts: [0, p-1] [p, q] [q+1, -1] ListNode lastNodeOfFirstPart = prev; ListNode lastNodeOfSubList = curr; ListNode next = null; for (int i = 0; curr != null && i < q - p + 1; ++i) { next = curr.next; curr.next = prev; prev = curr; curr = next; } // connect parts if (lastNodeOfFirstPart != null) lastNodeOfFirstPart.next = prev; else head = prev; lastNodeOfSubList.next = curr; return head; } } ``` #### JavaScript ``` javascript ``` #### Python ``` python ``` ### 分析 - 時間複雜度：$\mathcal{O}(n)$，其中 $n$ 為鏈結串列中的節點總數 - 空間複雜度：$\mathcal{O}(1)$ ## [例題] Reverse every K-element Sub-List ### 問題 ### 題解 ### 代碼 #### C++ ``` cpp ``` #### Java ``` java ``` #### JavaScript ``` javascript ``` #### Python ``` python ``` ### 分析 - 時間複雜度：$\mathcal{O}(n)$，其中 $n$ 為鏈結串列中的節點總數 - 空間複雜度：$\mathcal{O}(1)$ ## 參考資料 - [Coding Patterns: In-place Reversal of a Linked List | emre.me](https://emre.me/coding-patterns/in-place-reversal-of-a-linked-list/) - [Inplace Linked List Reversal Pattern | Astik Anand](https://astikanand.github.io/techblogs/coding-problem-patterns/inplace-linked-list-reversal-pattern)