题解 | 链表中环的入口结点

1、解题思路

快慢指针法（Floyd's Tortoise and Hare Algorithm）：

1. 判断是否有环：使用快慢指针，快指针每次移动两步，慢指针每次移动一步。如果两者相遇，说明有环；否则无环。
2. 找到环的入口：当快慢指针相遇时，将其中一个指针（如慢指针）重新指向链表头部。然后两个指针每次同时移动一步，再次相遇的节点即为环的入口。

数学证明：

• 设链表头到环入口的距离为 a，环入口到相遇点的距离为 b，相遇点到环入口的距离为 c。
• 快指针走的距离：a + b + c + b（因为快指针比慢指针多走一圈）。
• 慢指针走的距离：a + b。
• 因为快指针速度是慢指针的两倍，所以 2(a + b) = a + b + c + b => a = c。
• 因此，重新将一个指针指向头节点，两指针再次相遇时即为环的入口。

2、代码实现

C++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
  public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* slow = pHead, *fast = pHead;

        // 判断是否有环
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;  // 相遇, 有环
            }
        }

        // 无环的情况
        if (!fast || !fast->next) {
            return nullptr;
        }

        // 重新将一个指针指向头节点
        slow = pHead;

        // 两个指针同时移动, 直到再次相遇
        while ( slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        // 相遇点即为环的入口
        return slow;
    }
};

Java

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead, fast = pHead;

        // 判断是否有环
        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 = pHead;

        // 两个指针同时移动，直到再次相遇
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // 相遇点即为环的入口
        return slow;
    }
}

Python

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        slow, fast = pHead, pHead

        # 判断是否有环
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break  # 相遇，有环

        # 无环的情况
        if not fast or not fast.next:
            return None

        # 重新将一个指针指向头节点
        slow = pHead

        # 两个指针同时移动，直到再次相遇
        while slow != fast:
            slow = slow.next
            fast = fast.next

        # 相遇点即为环的入口
        return slow

3、复杂度分析

• 时间复杂度：O(n)，最多遍历链表两次。
• 空间复杂度：O(1)，只使用了两个指针。