題目:

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

給定一個linked list,確認它是否有循環結構在內

看到這個題目我的第一念頭就是hashset

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        record=[]
        if not head:
            return False
        while head.next:
            record.append(head)
            if head.next in record:
                return True
            head=head.next
        return False

一如既往的hash set
邊遍歷邊紀錄,一但發現一樣的點就回傳True,list結束都沒動靜回傳False
最後執行時間1476ms(faster than 5.01%)
嗯...,看來效率十分低下阿
這時我突然想到其實我根本不用紀錄,只要在路過的點"做記號"就好

於是我把所有路過點的值改為None,一但發現該點的值為None
就表示我們來到走過的地方(即循環存在),都沒發現就回傳False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        while head:
            if head.val==None:
                return True
            head.val=None
            head=head.next
        return False

最後執行時間47ms(faster than 99.39%)

但最後看討論區才發現原來這題要我們學的是龜兔賽跑演算法(Tortoise and Hare Algorithm)
所謂龜兔賽跑演算法是指如果list上存在環,從同一起點開始以不同速度前進的2個指標終將相遇
我們在程式上實作這個想法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        r=head
        t=head
        while r and r.next:
            r=r.next.next
            t=t.next
            if r==t:
                return True
        return False

設定兩個指標,一樣從頭開始
一個一次走一個Node,一個一次走兩個Node
若出現相遇的情形,則代表存在環,回傳True
若無,回傳False
最後執行時間52ms(faster than 97.45%)

本題學習到的重點:龜兔賽跑演算法(Tortoise and Hare Algorithm)
那我們下題見