LeetCode 筆記 - 160. Intersection of Two Linked Lists

Posted on Edited on

題目在此 160. Intersection of Two Linked Lists

給定一個 Linked list，它擁有兩個起點並最終會合併在一起
請計算出會合的節點

解題思維

在這裡我想介紹一下一個非常神奇又有趣的演算法 Floyd Cycle Detection Algorithm
也可以叫做 龜兔賽跑算法 (Tortoise and Hare Algorithm)

有關這個演算法可以看看這個影片

簡單來說用快慢指針各一，慢的指針每次都跑一步，快的指針每次都跑兩步

  1. 第一圈如果同時在同一個格上，表示有循環存在。
  2. 這時！把任一指針移動回起點，兩個指針每次都只走一步，相遇時就是循環起點
  3. 一個指針不動，一個繼續走，即可知道循環長度

好，回到題目

我們可以把整個 Linked list 分成幾個部分

  1. A 非重複的部分
  2. B 非重複的部分
  3. 重複的部分

這時我們可以使用兩個指針一起從 A, B 出發，從 A 出發的走到底就從 B 起點開始，反之亦然
這時候我們可以發現兩個指針都走過了 1, 2, 3 部分，所以長度是一樣的

所以這樣操作下來，他們兩個註定會在會合點相見

完成！

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:

        a = headA
        b = headB
        while a or b:
            
            if not a:
                a = headB
            if not b:
                b = headA
            
            if a == b:
                return a
            
            a = a.next
            b = b.next
            
        return None

😲