Two Pointer 快慢指標篇 – 陪你刷題

Leetcode 邁向千題的關卡，想要把所有題目刷過一遍，對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難，因此想要將刷題常用的觀念技巧與其對應題目整理出來，一方面可以整理自己思緒，也可以做為未來複習用。
這系列文章會一直持續下去，算是作為工程師職涯的隨身裝備。

今天要來探討的是 Two Pointer 雙指標的技巧，其中雙指標又可以分為快慢指標與左右指標，本篇將著重於快慢指標。

何謂快慢指標

快慢指標技巧是使用兩個指標以不同的速度向前移動來解決 linked list 相關問題的一種技巧。其中一個指標稱為「慢指標」，用於順序訪問 linked list 中每個節點；另一個指標稱為「快指標」，，它可以根據需求以更快的速度跳過某些節點。

利用快慢指標可以解決以下幾類 linked list 問題:

1. 剔除 sorted linked list 中的重複元素:快指標跳過重複元素，慢指標負責移除操作。

2. 判斷 linked list 是否成環:如果快慢指標最終指向同一個節點，則列表成環。

3. 尋找 linked list 的環起點:使用快慢指標找到環，然後重新定位慢指標找出環的起點。

4. 尋找 linked list 的中間節點:快指標跳兩步，慢指標跳一步，慢指標最終會指向中間。

5. 尋找 linked list 倒數第 K 個節點:快指標先向前走 K 步，然後快慢指標同時向前，慢指標指向的就是倒數第 K 個節點。

通過巧妙利用快慢指標的速度差，可以高效解決許多 linked list 算法問題。

(以下均以 walker 代稱慢指標， runner 代稱快指標)

將 sorted array 中重複元素剔除

要使用 Two Pointer 來處理 Array 的話，Array 本身一定要 sorted 過後，再使用才有意義。

透過 walker 紀錄上一個元素，再透過 runner 尋找下一個不重複的元素。

• Leetcode 對應題目 #26, #80

判斷 linked list 是否有環

walker 指標一次只能前進一個節點， runner 指標一次會前進兩個節點，若是兩個指標發生碰撞，代表在這個 linked list 中存在環。

該如何理解兩指標碰撞代表環存在？

如同在操場上跑步，跑的快的人最終都會超車跑的慢的人，兩個指標如果都進入到環中，最終跑的快的人會追上跑的慢的人。

判斷是否有環的操作框架

ListNode *walker = head, *runner = head;
while (runner != NULL && runner->next != NULL)
{
    walker = walker->next;
    runner = runner->next->next;
    if (walker == runner)
        return true;
}
return false;

• Leetcode 對應問題 #141

尋找 linked list 的環起點

尋找 linked list 的環起點，接續著上面的判斷 linked list 是否有環的問題，當 walker 和 runner 碰撞，將 walker 重新放到起點，接著 walker 和 runner 以一次一步的速度前進，當兩人再度碰撞，即代表他們位於環起點。
(詳細原理可以自行 google Floyd Cycle Detection Algorithm)

ListNode *walker = head, *runner = head;
while (runner != NULL && runner->next != NULL)
{
    walker = walker->next;
    runner = runner->next->next;
    if (walker == runner)
    {
        walker = head;
        while (walker != runner)
        {
            walker = walker->next;
            runner = runner->next;
        }
        return walker;
    }
}
return false;

• Leetcode 對應題目 #142

尋找 linked list 中間節點

如果 linked list 的節點個數是偶數的話，當 runner 走到 list 的末端且無法再前進時， walker 會在中間偏右的位置。

如果 linked list 的節點個數是奇數的話， walker 就在中間節點的位置。

Leetcode 對應題目 #234

這題要在 O(1) 的空間複雜度下，判斷單向 linked list 是否回文。

我們可以利用找中間節點的技巧，將 linked list 分成兩半，再將右半反轉。最後，比較兩半是否相同，即可判斷 linked list 是否回文。

判斷 linked list 是奇數還是偶數個節點，可以根據 runner 是否為空來判斷。

bool isPalindrome(ListNode* head) {
    ListNode *walker = head, *runner = head;
    while (runner != nullptr && runner->next != nullptr )
    {
        walker = walker->next;
        runner = runner->next->next;
    }
    // if runner != nullptr, list has odd number
    if (runner)
        walker = walker->next;
    ListNode *second_head = reverse_list(walker);
    while (second_head != nullptr)
    {
        if (second_head->val != head->val)
            return false;
        second_head = second_head->next;
        head = head->next;
    }
    return true;
}

尋找 linked list 上倒數 N 個節點

runner 先行走 N 個節點，接著 walker 和 runner 一起一次前進一步，當 runner 走到盡頭，walker 即位於倒數第 N 個節點。

Leetcode 對應題目 #19

這題除了透過雙指標，還可以使用哨兵節點來簡化處理 edge case 。

ListNode* removeNthFromEnd(ListNode* head, int n) {
    struct ListNode front(0, head);
    ListNode *walker = &front, *runner = &front;

    for (int i=0; i<n+1; i++)
    {
        runner = runner->next;
    }

    while (runner != nullptr)
    {
        walker = walker->next;
        runner = runner->next;
    }
    walker->next = walker->next->next;
    return front.next;
}

總結

當題目要求 in-place 進行操作，也就是限制 space complexity 為 O(1)，就可以想到 two pointers 技巧。
一個指標用於依序走遍所有元素，而另外一個指標的移動策略就是解題的關鍵。

還有一點需要注意的是，要使用 two pointer 處理資料前，資料必須經過排序，否則 two pointer 就派不上用場了。

延伸閱讀

1. Two Pointer 左右指標篇 - 陪你刷題
2. Sliding Window – 陪你刷題

參考資料

1. 雙指針技巧匯總 - labuladong
2. [Leetcode Article] Two-pointer Technique
3. [Leetcode Explore] Two-pointer Technique - Scenario II

Updated on 2023-10-01 22:02:42 星期日