Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。
今天要來探討的是 Two Pointer 雙指標的技巧,其中雙指標又可以分為快慢指標與左右指標,本篇將著重於快慢指標。
何謂快慢指標
透過一慢一快的兩個指標朝著同個方向前進,其中一個指標用於順序走訪 ,而另外一個則根據需求來訂定移動的策略,這樣的技巧通常用於解決 linked list 的各種問題。
利用快慢指標可以解決以下問題
- 將 sorted array 中重複元素剔除
- 判斷 linked list 是否有環
- 尋找 linked list 的環起點
- 尋找 linked list 的中間節點
- 尋找 linked list 上倒數第 K 個點
(以下均以 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
這題要判斷 linked list 是否回文,並且在 O(1) 的空間複雜度下。
由於 linked list 是單向的,這題就借助找 linked list 中間節點的技巧,找到後將右半部 linked list 反轉,再來比較兩個半邊的 linked list 是否一樣。
同時根據 runner 是否是 nullptr 來判斷 linked list 是奇數還是偶數個節點。
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 就派不上用場了。
延伸閱讀
參考資料
- 雙指針技巧匯總 - labuladong
- [Leetcode Article] Two-pointer Technique
- [Leetcode Explore] Two-pointer Technique - Scenario II
Updated on 2022-03-29 23:10:56 星期二