每日一题：链表中环的入口结点

判断链表环的入口节点

描述

给定一个链表，判断该链表是否存在环。如果存在环，返回环的入口节点；如果不存在环，返回NULL。

数据范围：

• 链表长度 $n$：$0\le n\le 10000$
• 链表中任意节点的值满足 $|val|\le 100000$

复杂度要求：

• 空间复杂度：$O(1)$
• 时间复杂度：$O(n)$

输入

• 输入一个链表的头节点 pHead，该链表可能包含环。

输出

• 如果链表存在环，返回环的入口节点；否则返回 NULL。

示例

示例 1：
输入：

{3, 2, 0, -4}, 1

返回值：

2

说明：

• 链表{3, 2, 0, -4}有一个环，环的入口节点是值为2的节点。

示例 2：
输入：

{1}, -1

返回值：

NULL

说明：

• 链表{1}没有环，返回NULL。

示例 3：
输入：

{-1, -7, 7, -4, 19, 6, -9, -5, -2, -5}, 6

返回值：

6

说明：

• 链表有环，环的入口节点是值为6的节点。

代码实现

/**
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * 找到链表中环的入口节点
 * 
 * @param pHead ListNode类 链表头结点
 * @return ListNode类 如果链表有环，返回环的入口节点，否则返回NULL
 */
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead) {
    // 判断链表是否为空或只有一个节点，若是则不存在环
    if (pHead == NULL || pHead->next == NULL) 
        return NULL;

    struct ListNode* fast = pHead->next->next;  // 快指针初始为第二个节点
    struct ListNode* slow = pHead->next;        // 慢指针初始为第一个节点

    // 快慢指针相遇判断是否有环
    while (fast != slow) {
        // 如果快指针到达链表末尾，则没有环
        if (fast == NULL || fast->next == NULL)
            return NULL;
        
        fast = fast->next->next;  // 快指针每次移动两步
        slow = slow->next;        // 慢指针每次移动一步
    }

    // 如果有环，重新初始化慢指针到链表头，从而找到环的入口
    slow = pHead;
    while (fast != slow) {
        fast = fast->next;  // 快指针每次移动一步
        slow = slow->next;  // 慢指针每次移动一步
    }

    // 快慢指针相遇时即为环的入口节点
    return slow;
}

思路解析

1. 快慢指针法判断是否有环：

   • 初始化两个指针 fast 和 slow，其中 fast 指针每次移动两步，slow 指针每次移动一步。
   • 如果链表存在环，快慢指针最终会在环内某个节点相遇；如果链表没有环，快指针会到达链表的尾部（即 fast == NULL 或 fast->next == NULL）。

2. 找到环的入口节点：

   • 当快慢指针相遇时，慢指针重新回到链表头节点，快指针保持在相遇节点处。
   • 然后，两个指针都每次移动一步，最终会在环的入口节点相遇。

3. 时间复杂度：

   • 快慢指针第一次相遇的时间复杂度为 $O(n)$，找到环的入口节点的时间复杂度也是 $O(n)$，所以总时间复杂度为 $O(n)$。

4. 空间复杂度：

   • 由于只使用了常数空间，因此空间复杂度为 $O(1)$。

注意事项：

• 需要确保链表为空或只有一个节点时，返回 NULL。
• 快指针每次移动两步，慢指针每次移动一步，可以有效地判断环并找到环的入口。