leetcode with python:141. Linked List Cycle

题目:

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 = Noneclass 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 = Noneclass 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 = Noneclass 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)
那我们下题见