Medium

题目描述

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 10^4] 内
  • -10^5 <= Node.val <= 10^5
  • pos 为 -1 或者链表中的一个有效索引

进阶： 你是否可以使用 O(1) 空间解决此题？

解题思路

本题有两种常见解法：

方法一：哈希表（直观解法） 使用哈希表存储访问过的节点，第一个重复出现的节点就是环的入口。这种方法简单直观，但需要 O(n) 的额外空间。

方法二：Floyd 判圈算法（推荐） 这是最优解法，使用两个指针解决问题，空间复杂度为 O(1)。

算法原理：

  1. 第一阶段：使用快慢指针检测是否有环。快指针每次走2步，慢指针每次走1步。如果有环，两指针必定相遇。
  2. 第二阶段：找环的入口。当快慢指针相遇后，将其中一个指针重置到链表头，然后两个指针都以每次1步的速度前进，再次相遇的节点就是环的入口。

数学原理：设链表头到环入口距离为a，环入口到相遇点距离为b，相遇点到环入口距离为c。相遇时慢指针走了a+b步，快指针走了a+b+c+b = a+2b+c步。由于快指针速度是慢指针的2倍，所以2(a+b) = a+2b+c，化简得a = c。这意味着从头节点和相遇点同时出发，每次走一步，相遇点就是环入口。

代码实现

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;
        
        // 第一阶段：检测是否有环
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }
        
        // 如果没有环
        if (!fast || !fast->next) return nullptr;
        
        // 第二阶段：找环的入口
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        
        return slow;
    }
};

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None
        
        # 第一阶段：检测是否有环
        slow = fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        else:
            # 没有环
            return None
        
        # 第二阶段：找环的入口
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        return slow

public class Solution {
    public ListNode DetectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        
        // 第一阶段：检测是否有环
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        
        // 如果没有环
        if (fast == null || fast.next == null) return null;
        
        // 第二阶段：找环的入口
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
}

var detectCycle = function(head) {
    if (!head || !head.next) return null;
    
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            slow = head;
            while (slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    
    return null;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希表O(n)O(n)
Floyd算法（推荐）O(n)O(1)

其中 n 为链表节点数。Floyd算法在最坏情况下需要遍历链表约1.5次，仍为线性时间复杂度，但空间复杂度为常数级别。

相关题目