美文网首页
链表是否有环

链表是否有环

作者: dalewong | 来源:发表于2021-10-20 15:37 被阅读0次

    https://leetcode-cn.com/problems/linked-list-cycle/submissions/
    判断链表是否有环 可以使用hashmap来存储是否之前有过
    但是由于题目要求只能o1的空间复杂度
    所以使用快慢指针来处理该问题

    需要注意的几点corner case,fast及slow node可能为空
    如果有环则slow会追上fast, 如果没有的话fast.next为空节点.

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            slow = head
            if not slow:
                return False
            fast = head.next
    
            if not (fast and fast.next):
                return False
    
            while slow != fast and fast and fast.next is not None:
                slow = slow.next
                fast = fast.next.next
            
            if slow == fast:
                return True
            else:
                return False
    

    https://leetcode-cn.com/problems/linked-list-cycle-ii/
    获取环形链表的交叉位置,一样o1的空间复杂度
    这里需要用一点证明
    假设从最开始到交点的距离为x, fast和slow交点为y, 环剩下的距离为z
    因为fast的速度是slow的一倍,所以fast的路径长度为slow的的一倍
    (x + y)* 2 = x + n(y + z) + y
    左右都去掉一个x + y, 则可得 x + y = n(y + z)
    x = (y + z)n - y
    x = (n-1)(y+z) + z
    由于我们知道y+z为一圈,所以从相交点走z和从头开始走x相遇的地方就位环的相交点

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def detectCycle(self, head: ListNode) -> ListNode:
            current = fast = slow = head
            if not (fast and fast.next):
                return 
            
            # 这里因为slow和fast一样 所以需要先slow和fast都走一步再循环往前走
            fast = fast.next.next
            slow = slow.next
            while fast != slow and fast and fast.next:
                fast = fast.next.next
                slow = slow.next
            
            if fast != slow:
                return
            
            while current != fast:
                current = current.next
                fast = fast.next
            
            return current
    

    相关文章

      网友评论

          本文标题:链表是否有环

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