141/142. Linked List Cycle I/II

  1. 判断链表是否有环.
    用快慢指针,注意点在于考虑清楚链表长度为0,1,2,3的情况。while循环判断条件建议用fast != slow
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False

        slow = head.next
        fast = head.next.next

        while fast != slow:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True
  1. 找到入环点。注意点在于初始化的时候让slow先走一步,fast先走两步,始终保持1:2的关系。
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return None

        slow = head.next
        fast = head.next.next

        while fast != slow:
            if not fast or not fast.next:
                return None
            fast = fast.next.next
            slow = slow.next

        cur = head
        while cur != slow:
            cur = cur.next
            slow = slow.next
        return cur
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容