图书馆网站建设研究网站上做旅游卖家要学什么条件

判断链表环的入口节点

描述

给定一个链表，判断该链表是否存在环。如果存在环，返回环的入口节点；如果不存在环，返回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。
• 快指针每次移动两步，慢指针每次移动一步，可以有效地判断环并找到环的入口。