美文网首页Leetcode刷题笔记
第二十九天 Linked List Cycle

第二十九天 Linked List Cycle

作者: 业余马拉松选手 | 来源:发表于2018-09-18 02:56 被阅读5次

    嗯,校招笔试判卷子,到现在

    先做一道水题吧:https://leetcode-cn.com/problems/linked-list-cycle/description/

    除了用一个字典之类的容器存储之外,还可以利用快慢指针的方法,通过一次遍历就来解决这个问题:

    一个走一步,一个走两部,如果俩个碰上来,那么就是有环,如果快指针先指向了None的话,就是没有环的

    代码很直接:

    # 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
            """
            if head == None or head.next == None:
                return False
            slow = head
            fast = head.next
            while fast != slow:
                if fast == None or fast.next == None:
                    return False
                else:
                    slow = slow.next
                    fast = fast.next.next
            return True
    

    相关文章

      网友评论

        本文标题:第二十九天 Linked List Cycle

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