十佳深圳网站设计,网站建设需要提供什么,凡科快图官方,友情链接的形式有哪些文章目录 判断链表环的入口节点描述数据范围#xff1a;复杂度要求#xff1a;输入输出 示例代码实现思路解析注意事项#xff1a; 判断链表环的入口节点 描述
给定一个链表#xff0c;判断该链表是否存在环。如果存在环#xff0c;返回环的入口节点#xff1b;如果不存… 文章目录 判断链表环的入口节点描述数据范围复杂度要求输入输出 示例代码实现思路解析注意事项 判断链表环的入口节点 描述
给定一个链表判断该链表是否存在环。如果存在环返回环的入口节点如果不存在环返回NULL。
数据范围
链表长度 n n n 0 ≤ n ≤ 10000 0 \leq n \leq 10000 0≤n≤10000链表中任意节点的值满足 ∣ v a l ∣ ≤ 100000 |val| \leq 100000 ∣val∣≤100000
复杂度要求
空间复杂度 O ( 1 ) O(1) O(1)时间复杂度 O ( n ) O(n) 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;
}思路解析 快慢指针法判断是否有环 初始化两个指针 fast 和 slow其中 fast 指针每次移动两步slow 指针每次移动一步。如果链表存在环快慢指针最终会在环内某个节点相遇如果链表没有环快指针会到达链表的尾部即 fast NULL 或 fast-next NULL。 找到环的入口节点 当快慢指针相遇时慢指针重新回到链表头节点快指针保持在相遇节点处。然后两个指针都每次移动一步最终会在环的入口节点相遇。 时间复杂度 快慢指针第一次相遇的时间复杂度为 O ( n ) O(n) O(n)找到环的入口节点的时间复杂度也是 O ( n ) O(n) O(n)所以总时间复杂度为 O ( n ) O(n) O(n)。 空间复杂度 由于只使用了常数空间因此空间复杂度为 O ( 1 ) O(1) O(1)。
注意事项
需要确保链表为空或只有一个节点时返回 NULL。快指针每次移动两步慢指针每次移动一步可以有效地判断环并找到环的入口。
