↓Skip to main content
  1. Posts/

LeetCode-142 环形链表 II

·1 min·
Table of Contents

LeetCode-142 环形链表 II #

Solution 1 #

设链表头到入口节点的距离为 $a$, 环长为 $b$, 快慢指针相遇时，快指针走过了 $n$ 圈, 慢指针走过了 $c$ 步. 有 $c = 2c-c = nb$. 此时 c 距离环入口的距离为 $nb - (nb-a) = a$, 和链表头到入口的距离相等. 因此, 从链表头和相遇点同时出发, 两个指针相遇的地方即为环的入口.

代码如下:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                while slow != head:
                    slow = slow.next
                    head = head.next
                return slow
        return None