This page looks best with JavaScript enabled

Leetcode 142 Linked List Cycle II

題目大意

  • 輸入一 linked list, 如果這個 linked list 有循環存在,回傳循環的起點
  • linked list 的長度為 0~104
  • 基本方法做完之後有一個 O(1) space 的 follow up
  • 不可竄改 linked list

Problem

https://leetcode.com/problems/linked-list-cycle-ii/

My Solution

簡單作法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        nodes = set()
        while head:
            if head in nodes:
                return head
            nodes.add(head)
            head = head.next
        return None

follow up

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        l = c = r = head
        while r and r.next:
            r = r.next.next
            c = c.next
            if r is c:
                # cycle exist
                while l is not c:
                    c = c.next
                    l = l.next
                return c # same as l
        return None
  • 為了方便理解,先標示出左中右三個 pointer, 都先指著開頭
  • 先使用中、右 兩個指標,搭配 Leetcode 141 的方法 判斷有沒有循環
  • 若有循環,左, 中, 右三者目前走的步數 (index-0) 分別為: (0, 1k, 2k)
  • 1k 及 2k 是同一個 node
  • 現在使用左, 中 兩個指標從 (0, 1k) 開始,兩者都一次一步走向 (1k, 2k)
  • 左、中第一次相遇的位置就是循環的起點,且不一定是在 (1k, 2k),可能是比較早的位置

為什麼第一次相遇是循環的起點?

  • (左,中) 經過的路線: (0, 1k) -> (a, a) -> (1k, 2k),值得注意的是,如果 0~a 比 k~a 大,代表有多繞循環
  • 如果把上述路線反推回去會很直覺的發現,因為 1k 及 2k 是同一個 node, 理所當然他們到 a 的步數相同