This page looks best with JavaScript enabled

Leetcode 141 Linked List Cycle

題目大意

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

Problem

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

My Solution

簡單作法

  • 使用內建資料結構set紀錄所有走過的 node
  • 如果重複則表示是循環
  • 可以走到底表示不是循環
 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 hasCycle(self, head: ListNode) -> bool:
        nodes = set()
        while head:
            if head in nodes:
                return True
            nodes.add(head)
            head = head.next
        return False

follow up

  • 使用兩個 pointer ,起始點為前兩個 node ,因此排除空 linked list ,但不排除一個 linked list ,因為可能自己的 next 指向自己
  • 左邊的一次一步,右邊的一次兩步
  • 如果有循環的話,兩個 pointer 一定會在某處相遇 -> 為何一定會相遇
  • 因為右邊走比較快,且一次兩步,所以只要判斷右邊 & 右邊的 next 非空就好,判斷左邊的話會重複沒必要
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return False
        l, r = head, head.next
        while r and r.next:
            if l is r:
                return True
            l = l.next
            r = r.next.next
        return False

為何一定會相遇

假設:

  • 現在有一個循環(也是單向),他有n 個元素
  • 慢、快兩者距離 k steps

說明:

  • 下一個步驟,也就是慢 +1 & 快 +2之後,他們的距離會變成 k+1
  • 再下一個步驟,會變成k+2,也就是說 k_new = (k+1) mod n
  • 因為是循環,總有一天距離會變成 0
  • 所以目前的距離m 的 range 為: 0 <= m <= n-1

follow up 改良 (因為寫了 Leetcode 142 )

l, r 起始點都從頭開始

1
2
3
4
5
6
7
8
9
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        l = r = head
        while r and r.next:
            l = l.next
            r = r.next.next
            if l is r:
                return True
        return False