企业电子网站建设百度大数据官网

一.题目及剖析

https://leetcode.cn/problems/linked-list-cycle-ii/description/

这道题就是找到链表中环的入口

二.思路引入

假设起点到环的入口的距离为L, 环的长度为C, 入口到相遇点的距离为C - N

设定一个快慢指针,速度分别为2, 1

则有 (L + kC - N) = 2*(L + C - N)

即L = (k - 1)C + N

说明,如果我设定两个速度相同的指针,一个从起点开始遍历,一个从相遇点开始遍历,那么它们会在入口处碰撞

三.代码引入

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {if(head == NULL || head->next == NULL)return NULL;struct ListNode* fast, * slow;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){struct ListNode* meet = fast;while(meet != head){meet = meet->next;head = head->next;}return meet;}}return NULL;
}

四.思路扩展

这道题如果将这个带还链表从相遇点断开,那么其实就是一个相交链表,交点就是环的入口