美文网首页
Linked List Cycle链列环

Linked List Cycle链列环

作者: 穿越那片海 | 来源:发表于2017-03-13 10:13 被阅读0次

    Easy

    给定一个链列,确定它是否包含一个环。不要使用额外的存储。

    Solution

    什么是链列环?
    下图做个直观的解释:进入链列走到6后,下一步为3,下一步为1,在下一步为6,。。。,进入循环,所以存在一个环6->1->3->6。

    链列环

    既然有环,就可以想象为环形跑道赛跑的问题,快跑者一定会在某个时间点追上慢跑者(体力无限)。下面的解法,就虚拟了一个慢跑者,一个快跑者,如果某个时间点,两人都进入循环跑道,则证明环存在。此外这个算法还利用了try...Except...的trick,当链列为空或者链列走到末位的时候,try模块的code都会返回错误,进入except, 而这两种错误的情况就是没有环的。

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def hasCycle(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            try:
                slow = head
                fast = head.next
                while slow is not fast:
                    slow = slow.next
                    fast = fast.next.next
                return True
            except:
                return False
                
            
    

    相关文章

      网友评论

          本文标题:Linked List Cycle链列环

          本文链接:https://www.haomeiwen.com/subject/rlrfnttx.html