Leetcode 141. Linked List Cycle -

給定一組linked list ，判斷linked list是否存在迴圈

Python

方法一 : 快慢指針

設置快慢指針，快指針每次移動兩步，慢指針只移動1步。如果有循環，那麼快慢指針最終會重合

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow=head
        fast=head
        
        while fast and fast.next:
            slow=slow.next          #移動1步
            fast=fast.next.next     #移動兩步
            
            if slow==fast:          #重合，表示有迴圈
                return True
        return False

方法二 : 路過點設None

把路過的點設None，如果遇到下一個None表示有走過(有迴圈)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        while head:
            if head.val==None:   #遇到下一個None
                return True
            head.val=None        #路過的點設None
            head=head.next
        return False

C++

快慢指針

定義兩個指針，分別為 slow 和 fast。 slow 每次移動一步，而 fast 每次移動兩步。如果鍊錶中有環，那麼 fast 指針最終一定會追上 slow 指針。

如果鍊錶中沒有環，那麼 fast 指針會先到達鍊錶的末尾，此時我們就可以判斷鍊表中沒有環。

時間複雜度：O(n)。其中，n 是鍊錶中的節點數目。

空間複雜度：O(1)。我們只使用了兩個指針。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr) {
            return false;
        }
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
};

Python

C++

相關