0141. Linked List Cycle - chasel2361/leetcode GitHub Wiki

Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.
If pos is -1, then there is no cycle in the linked list.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

這題的目的在於確認串鍊中的最後一個節點是否連接回原本的串鍊中，此時可以使用兩個移動速度不同的節點檢視串鍊，慢的一次前進一個節點，慢的一次前進兩個節點，如果串鍊沒有循環，那較快的節點就會碰到 null，若存在循環，由於速度剛好差一倍，當慢速結點走完一個循環時，快速節點也會剛好走完第二圈，兩者必定停於同一個節點，此時即可判定串鍊中含有循環，程式碼如下。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next or not head.next.next: return False
        slow = head.next
        fast = slow.next
        while slow != fast:            
            if not slow.next or not fast.next or not fast.next.next: 
                return False
            else:
                slow = slow.next
                fast = fast.next.next            
        return True

這樣寫的時間複雜度為 O(N)，空間複雜度為 O(1)

參考別人的寫法之後發現可以精簡一點，把進入迴圈的條件設定為 fast 與 fast.next 存在，如此進入迴圈後就只要判斷 slow 與 fast 是否相同即可

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next: return False
        slow = head.next
        fast = slow.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

這樣寫的時間複雜度為 O(N)，空間複雜度為 O(1)

Code Link