美文网首页
142. Linked List Cycle II

142. Linked List Cycle II

作者: 羲牧 | 来源:发表于2020-05-31 12:53 被阅读0次

    寻找有环链表环的起点。

    假设头节点距离环的起点距离为a, 起点距离第一次相遇点为b, 环长L
    则有a+b+kL = 2(a+b),即a+b=kL

    由于a=kL-b, 让两个指针分别从相遇点和头节点处出发,则二者会在环的起点处相遇。

    # 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:
            if head is None or head.next is None:
                return None
            fast = head
            slow = head
            while fast.next and fast.next.next:
                fast = fast.next.next
                slow = slow.next
                if slow == fast:
                    break
            if fast.next is None or fast.next.next is None:
                return None
            
            slow = head
            while fast != slow:
                fast = fast.next
                slow = slow.next
            return fast
            
    

    相关文章

      网友评论

          本文标题:142. Linked List Cycle II

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