题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个环形链表，如果有环，现在要找到这个链表环的入口。

思路分享

  • 前置知识都在 【Leetcode Daily】141环形链表 和下面引用的题解里，不再赘述。

    https://leetcode.cn/problems/linked-list-cycle-ii/solutions/

  • 这里主要是想说明怎么想通 a=(k-1)*(b+c) +c 是怎么到头指针和慢指针的相遇点做答案的。这个式子的意思是，头指针走到环入口的距离和在环里转 k-1 圈再走 c 步相等。此时此刻，慢指针在环里走了 b 步，不管走多少圈，再走 c 步就到环入口。这正是两个指针相遇作为答案的依据。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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]:
        slow, fast = head, head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                while head != slow:
                    head, slow = head.next, slow.next
                return head
        return None