寻找有环链表环的起点。
假设头节点距离环的起点距离为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
网友评论