南昌集团网站建设公司,广西高端网站建设公司,sem 推广软件,wordpress 招聘网站10.环形链表2
142. 环形链表 II - 力扣#xff08;LeetCode#xff09; /*
解题思路#xff1a;
如果链表存在环#xff0c;则fast和slow会在环内相遇#xff0c;定义相遇点到入口点的距离为X,定义环的长度为C,定义头到入口的距离为L,fast在slow进入环之后一圈内追上slow…10.环形链表2
142. 环形链表 II - 力扣LeetCode /*
解题思路
如果链表存在环则fast和slow会在环内相遇定义相遇点到入口点的距离为X,定义环的长度为C,定义头到入口的距离为L,fast在slow进入环之后一圈内追上slow,则会得知
slow所走的步数为:L X
fast所走的步数为L X N * C
并且fast所走的步数为slow的两倍故
2*(L X) L X N * C
即 L N * C - X
所以从相遇点开始slow继续走让一个指针从头开始走相遇点即为入口节点
*/typedef struct ListNode Node;
struct ListNode *detectCycle(struct ListNode *head) {Node* slow head;Node* fast head;while(fast fast-next){slow slow-next;fast fast-next-next;//走到相遇点if(slow fast){// 求环的入口点Node* meet slow;Node* start head;while(meet ! start){meet meet-next;start start-next;}return meet;}}return NULL;
}
