刷題模式: 快慢指針（Fast-slow Pointers）

--- title: "刷題模式: 快慢指針（Fast-slow Pointers）" description: "Patterns for Coding Questions: Fast-slow Pointers." image: https://i.imgur.com/lMvTf2e.png author: Hsins tags: LeetCode, Coding Interview robots: breaks: GA: disqus: --- # 快慢指針（Fast-slow Pointers） <img src="https://i.imgur.com/lMvTf2e.png" height=200/> > 本篇內容主要為 [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。 ## 重點整理 - 快慢指針（Fast-slow Pointers）又稱龜兔演算法（Hare & Tortoise Algorithm） - 策略：使用兩個不同速度的指針遍歷線性結構（陣列、序列、鏈結串列） - 題型： - 環狀鏈表、環狀陣列 - 鏈表判斷迴圈、鏈表判斷長度、鏈表迴圈操作 ## 題目匯總 - `0141` [[英]](https://leetcode.com/problems/linked-list-cycle/) [[中]](https://leetcode-cn.com/problems/linked-list-cycle/) Linked List Cycle - `0142` [[英]](https://leetcode.com/problems/linked-list-cycle-ii/) [[中]](https://leetcode-cn.com/problems/linked-list-cycle-ii/) Linked List Cycle II - `0143` [[英]](https://leetcode.com/problems/reorder-list/) [[中]](https://leetcode-cn.com/problems/reorder-list/) Recorder List - `0202` [[英]](https://leetcode.com/problems/happy-number/) [[中]](https://leetcode-cn.com/problems/happy-number/) Happy Number - `0234` [[英]](https://leetcode.com/problems/palindrome-linked-list/) [[中]](https://leetcode-cn.com/problems/palindrome-linked-list/) Palindrome Linked List - `0457` [[英]](https://leetcode.com/problems/circular-array-loop/) [[中]](https://leetcode-cn.com/problems/circular-array-loop/) Circular Array Loop - `0876` [[英]](https://leetcode.com/problems/middle-of-the-linked-list/) [[中]](https://leetcode-cn.com/problems/middle-of-the-linked-list/) Middle of the Linked List ## [例題] 環形鏈表（Linked-List Cycle） ### 問題給定一個單向鏈結串列（Singly Linked-list）的頭部節點，撰寫一支函數判斷這個鏈結串列是否存在迴圈（cycle）。 <img src="https://i.imgur.com/QZESX46.png" /> ### 題解想像有兩位跑者在圓形操場上奔跑，如果其中一位跑者的速度比另外一位跑者要來的快，那麼勢必會趕上並從後面越過較慢的跑者。這樣的思路可以用來設計一種演算法，來確定鏈結串列是否存在迴圈。分別採用慢速指針 `slow` 和快速指針 `fast` 遍歷鏈結串列，每次執行時讓慢速指標移動一步，快速指標移動兩步。可以得到以下事實： 1. 如果鏈結串列沒有迴圈，則 `fast` 會先抵達鏈結串列的末端 2. 如果鏈結串列沒有迴圈，則 `slow` 永遠不會與 `fast` 相遇如果鏈結串列存在迴圈，則 `fast` 和 `slow` 先後進入該迴圈。並且在此之後，兩個指針會在迴圈中無限移動。如果在一階段兩個指針相遇了，就可以得到「鏈結串列存在迴圈」的結論。接下來讓我們分析一下這兩個指針是否有可能相遇。當 `fast` 從後面接近 `slow` 時，有兩種可能性： 1. `fast` 比 `slow` 慢一步 2. `fast` 比 `slow` 慢兩步快指標和慢速指標之間的所有其他距離將減少到這兩種可能性之一。讓我們分析一下這些場景，考慮到快速指標總是先移動： - 如果 `fast` 比 `slow` 慢一步：`fast` 移動兩步，`slow` 移動一步，彼此相遇 - 如果 `fast` 比 `slow` 慢兩步：`fast` 移動兩步，`slow` 移動一步，等同上一場景，意味兩個指針將在下一次反覆運算中相遇由上述分析可知：如果鏈接串列中存在迴圈，則兩個指針必定會相遇。上述討論的直觀表示如圖所示： <img src="https://i.imgur.com/qApx8VZ.png" /> ### 代碼 #### C++ ``` cpp class LinkedListCycle { public: static bool hasCycle(ListNode *head) { ListNode *slow = head; ListNode *fast = head; while (fast != nullptr && fast-> != nullptr) { fast = fast->next->next; slow = slow->next; if (slow == fast) return true; } return false; } } ``` #### Java ``` java class LinkedListCycle { public static boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) return true; } return false; } } ``` #### JavaScript ``` javascript const findCycleLength = (head) => { let slow = head; let fast = head; while (fast && fast.next) { fast = fast.next.next; slow = slow.next; if (slow === fast) return true; } return false; } ``` #### Python ``` python def has_cycle(head): slow, fast = head, head while fast and fast.next: fast = fast.next.next slow = slow.next if slow == fast: return True return False ``` ### 分析 - **時間複雜度**：$\mathcal{O}(n)$，其中 $n$ 為 Linked-List 中的節點總數 - **空間複雜度**：$\mathcal{O}(1)$ ## [補充] 環狀鏈表的迴圈長度（Linked-List Cycle Length） ### 題目給定一個單向鏈結串列（Singly Linked-list）的頭部節點，撰寫一支函數獲取這個鏈結串列的迴圈長度。 ### 題解 1. 先透過 `slow` 和 `fast` 指針找到相遇位置 2. 紀錄相遇位置並讓 `slow` 繼續走，同時記錄步數，當其返回原點時，經過的步數即為迴圈長度 ### 代碼 #### C++ ``` cpp class LinkedListCycleLength { public: static bool findCycleLength(ListNode *head) { ListNode *slow = head; ListNode *fast = head; while (fast != nullptr && fast-> != nullptr) { fast = fast->next->next; slow = slow->next; if (slow == fast) return calculateLength(slow); } return false; } private: static int calculateLength(ListNode *slow) { ListNode *curr = slow; int cycleLength = 0; do { curr = curr->next; cycleLength++; } while (curr != slow); return cycleLength; } } ``` #### Java ```java class LinkedListCycleLength { public static int findCycleLength(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) return calculateLength(slow); } return 0; } private static int calculateLength(ListNode slow) { ListNode curr = slow; int cycleLength = 0; do { curr = curr.next; cycleLength++; } while (curr != slow); return cycleLength; } } ``` #### JavaScript ``` javascript const findCycleLength = (head) => { let slow = head; let fast = head; while (fast && fast.next) { fast = fast.next.next; slow = slow.next; if (slow === fast) return calculateCycleLength(slow); } } const calculateCycleLength = (slow) => { let curr = slow; let cycle_length = 0; while (true) { curr = curr.next; cycle_length += 1; if (curr === slow) break; } return cycle_length; } ``` #### Python ``` python def find_cycle_length(head): slow, fast = head, head while fast and fast.next: fast = fast.next.next slow = slow.next if slow == fast: return calculate_cycle_length(slow) return False def calculate_cycle_length(slow): curr = slow cycle_length = 0 while True: curr = curr.next cycle_length += 1 if curr == slow: break return cycle_length ``` ### 分析 - **時間複雜度**：$\mathcal{O}(n)$，其中 $n$ 為 Linked-List 中的節點總數 - **空間複雜度**：$\mathcal{O}(1)$ ## [例題] 鏈表的環狀入口（Start of Linked-List Cycle） ### 問題給定一個單向鏈結串列（Singly Linked-list）的頭部節點，撰寫一支函數獲取這個鏈結串列的迴圈入口結點。 <img src="https://i.imgur.com/jAFCJpZ.png" /> ### 題解如果我們能夠知道鏈結串列的迴圈長度，可以透過以下步驟找到迴圈入口： 1. 取兩個指針分別為 `pointer1` 和 `pointer2` 2. 初始化指針指向鏈結串列的起始點 3. 透過 **快慢指針（fast-slow pointers）** 方法獲取迴圈長度 $K$ 4. 使 `pointer2` 向前移動 $K$ 個結點 5. 再讓 `pointer1` 和 `pointer2` 同步向前移動直到相遇 6. 由於 `pointer1` 與 `pointer2` 相差 $K$ 個結點，當兩者相遇時 `pointer2` 已經走完了一圈，他們相遇的點就是迴圈入口 <img src="https://i.imgur.com/G2qzd4B.png" /> ### 代碼 #### C++ ``` cpp class LinkedListCycleStart { public: static ListNode *findCycleStart(ListNode *head) { int cycleLength = 0; ListNode *slow = head; ListNode *fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { cycleLength = calculateCycleLength(slow); break; } } return findStart(head, cycleLength); } private: static int calculateCycleLength(ListNode *slow) { ListNode *curr = slow; int cycleLength = 0; do { curr = curr->next; cycleLength++; } while (curr != slow); return cycleLength; } static ListNode *findStart(ListNode *head, int cycleLength) { ListNode *pointer1 = head; ListNode *pointer2 = head; while (cycleLength > 0) { pointer2 = pointer2->next; cycleLength--; } while (pointer1 != pointer2) { pointer1 = pointer1->next; pointer2 = pointer2->next; } return pointer1; } } ``` #### Java ``` java class LinkedListCycleStart { public static ListNode findCycleStart(ListNode head) { int cycleLength = 0; ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow === fast) { cycleLength = calculateCycleLength(slow); break } } return findStart(head, cycleLength); } private static int calculateCycleLength(ListNode slow) { ListNode curr = slow; int cycleLength = 0; do { curr = curr.next; cycleLength++; } while (curr != slow); return cycleLength; } private static ListNode findStart(ListNode head, int cycleLength) { ListNode pointer1 = head; ListNode pointer2 = head; while (cycleLength > 0) { pointer2 = pointer2.next; cycleLength--; } while (pointer1 != pointer2) { pointer1 == pointer1.next; pointer2 == pointer2.next; } return pointer1; } } ``` #### JavaScript ``` javascript const find_cycle_start = (head) => { let cycle_length = 0; let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) { cycle_length = calculate_cycle_length(slow); break; } } return find_start(head, cycle_length); } const calculate_cycle_length = (slow) => { let curr = slow; let cycle_length = 0; while (true) { curr = curr.next; cycle_length += 1; if (curr === slow) break; } return cycle_length; } const find_start = (head, cycle_length) { let pointer1 = head; let pointer2 = head; while (cycle_length > 0) { pointer2 = pointer2.next; cycle_length -= 1; } while (pointer1 !== pointer2) { pointer1 = pointer1.next; pointer2 = pointer2.next; } return pointer1; } ``` #### Python ``` python def find_cycle_start(head): cycle_length = 0 slow, fast = head, head while (fast and fast.next): fast = fast.next.next slow = slow.next if slow == fast: cycle_length = calculate_cycle_length(slow) break return find_start(head, cycle_length) def calculate_cycle_length(slow): curr = slow cycle_length = 0 while True: curr = curr.next cycle_length += 1 if curr == slow: break return cycle_length def find_start(head, cycle_length): pointer1 = head pointer2 = head while cycle_length > 0: pointer2 = pointer2.next cycle_length = cycle_length - 1 while pointer1 != pointer2; pointer1 = pointer1.next pointer2 = pointer2.next return pointer1 ``` ### 分析 - **時間複雜度**：$\mathcal{O}(n)$ - **空間複雜度**：$\mathcal{O}(1)$ ## [例題] 快樂數（Happy Number） ### 問題如果一個數字 **反覆取其各位數字的平方和後結果為 $1$** 稱其為 [快樂數（Happy Number）](https://en.wikipedia.org/wiki/Happy_number)；其他不符合的數字則會被困於一個不包括 $1$ 的迴圈當中。 **Examples** ``` Input: 23 Output: true (23 is a happy number) ``` $$ \begin{align*} 2^2 + 3^2 &= 13 \\ 1^2 + 3^2 &= 10 \\ 1^2 + 0^2 &= 1 \end{align*} $$ ``` Input: 12 Output: false (12 is not a happy number) ``` $$ \begin{align*} 1^2 + 2^2 &= 5 \\ 5^2 &= 25 \\ 2^2 + 5^2 &= 29 \\ 2^2 + 9^2 &= 85 \\ 8^2 + 5^2 &= 89 \\ 8^2 + 9^2 &= 145 \\ 1^2 + 4^2 + 5^2 &= 42 \\ 4^2 + 2^2 &= 20 \\ 2^2 + 0^2 &= 4 \\ 4^2 &= 16 \\ 1^2 + 6^2 &= 37 \\ 3^2 + 7^2 &= 58 \\ 5^2 + 8^2 &= 89 \\ \end{align*} $$ 寫一支程式判斷一個數字是不是快樂數字。 ### 題解如同題目中所述，如果一個數字是快樂數，在反覆計算的過程中會停駐在數字 $1$ 上（下次計算仍得到 $1$ 這個結果）；如果一個數字不是快樂數，在反覆計算的過程中，會不斷地在特定數字重複，比如第二個範例的 $89$。因此我們可以建立一個鏈結串列儲存計算過程所得到的數字，並透過 **快慢指針（fast-slow pointers）** 找到迴圈的入口，檢查該數字是否為 $1$ 或是其他數字。 ### 代碼 #### C++ ``` cpp class HappyNumber { public: static bool find(int num) { int slow = num, fast = num; do { slow = findSquareSum(slow); fast = findSquareSum(findSquareSum(fast)); } while (slow != fast); return slow == 1; } private: static int findSquareSum(int num) { int sum = 0, digit; while (num > 0) { digit = num % 10; sum += digit * digit; sum /= 10; } return sum; } ``` #### Java ``` java class HappyNumber { public static boolean find(int num) { int slow = num; int fast = num; do { slow = findSquareSum(slow); fast = findSquareSum(findSquareSum(fast)); } while (slow != fast); return slow == 1; } private static int findSquareSum(int num) { int sum = 0; int digit; while (num > 0) { digit = num % 10; sum += digit * digit; num /= 10; } return sum; } } ``` #### JavaScript ``` javascript const find_happy_number = (num) => { let slow = num; let fast = num; while (true) { slow = find_square_sum(slow); fast = find_square_sum(find_square_sum(fast)); if (slow === fast) break; } return slow === 1; } const find_square_sum = (num) => { let sum = 0; while (num) { sum = sum + Math.pow(num % 10, 2); num = Math.floor(num / 10); } return sum; } ``` #### Python ``` python def find_happy_number(num): slow, fast = num, num while True: slow = find_square_sum(slow) fast = find_square_sum(find_square_sum(fast)) if slow == fast: break return slow == 1 def find_square_sum(num): res = 0 while (num > 0): digit = num % 10 res = res + digit * digit num = num // 10 return res ``` ### 分析 - **時間複雜度**：$\mathcal{O}(\log{n})$ - 數字 $n$ 的位數 $M = \log{} (n+1)$ - 其平方和最多為 $81M$（當所有位數都是 $9$ 時） - $n_{\text{next}} < 81 \log(n+1)$ - **空間複雜度**：$\mathcal{O}(1)$ ## [例題] 鏈表的中間結點（Middle of the Linked-List） ### 問題給定一個單向鏈結串列（Singly Linked-list）的頭部節點，撰寫一支函數獲取鏈結串列的中間結點。 **Example** ``` Input: 1 -> 2 -> 3 -> 4 -> 5 -> null Output: 3 Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null Output: 4 Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null Output: 4 ``` ### 題解一種直觀的策略是先遍歷鏈結串列獲取長度後，在第二次反覆運算中找到中間結點。除此之外，我們也能透過快慢指針（fast-slow pointers）方法，使 `fast` 指針的步長始終是 `slow` 指針的兩倍，如此一來當 `fast` 抵達鏈結串列的末端時，恰好 `slow` 就位在中間結點上。 ### 代碼 #### C++ ``` cpp class MiddleOfLinkedList { public: static ListNode *findMiddle(ListNode *head) { ListNode *slow = head; ListNode *fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; } } ``` #### Java ``` java class MiddleOfLinkedList { public static ListNode findMiddle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } } ``` #### JavaScript ``` javascript const findMiddleOfLinkedList = (head) => { let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; fast = afst.next.next; } return slow; } ``` #### Python ``` python def find_middle_of_linked_list(head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow ``` ### 分析 - **時間複雜度**：$\mathcal{O}(n)$，其中 $n$ 為 Linked-List 中的節點總數 - **空間複雜度**：$\mathcal{O}(1)$ ## 參考資料 - [Coding Patterns: Fast & Slow Pointers | emre.me](https://emre.me/coding-patterns/fast-slow-pointers/)  {%hackmd @Hsins/widget-license %}