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

文章目录

判断链表环的入口节点
- 描述
- - 数据范围：
  - 复杂度要求：
  - 输入
  - 输出
- 示例
- 代码实现
- 思路解析
- 注意事项：

判断链表环的入口节点

在这里插入图片描述

描述

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

数据范围：

链表长度 $n$ ： $\leq n \leq 10000$
链表中任意节点的值满足 $\leq 100000$

复杂度要求：

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

输入

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

输出

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

示例

示例 1：
输入：

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

返回值：

说明：

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

示例 2：
输入：

{1}, -1

返回值：

NULL

说明：

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

示例 3：
输入：

{-1, -7, 7, -4, 19, 6, -9, -5, -2, -5}, 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;
}

思路解析

快慢指针法判断是否有环：
- 初始化两个指针 fast 和 slow，其中 fast 指针每次移动两步，slow 指针每次移动一步。
- 如果链表存在环，快慢指针最终会在环内某个节点相遇；如果链表没有环，快指针会到达链表的尾部（即 fast == NULL 或 fast->next == NULL）。
找到环的入口节点：
- 当快慢指针相遇时，慢指针重新回到链表头节点，快指针保持在相遇节点处。
- 然后，两个指针都每次移动一步，最终会在环的入口节点相遇。
时间复杂度：
- 快慢指针第一次相遇的时间复杂度为 $O (n)$ ，找到环的入口节点的时间复杂度也是 $O (n)$ ，所以总时间复杂度为 $O (n)$ 。
空间复杂度：
- 由于只使用了常数空间，因此空间复杂度为 $O (1)$ 。