[leetcode] 142. Linked List Cycle II

[leetcode] 142. Linked List Cycle II

Description

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1Output: tail connects to node index 1Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0Output: tail connects to node index 0Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1Output: no cycleExplanation: There is no cycle in the linked list.

Follow up:

Can you solve it without using extra space?

分析

题目的意思是：找到一个链表的的环的起点，没有则返回NULL。

X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置，则根据快指针速度为慢指针速度的两倍，可以得出： 2*(a + b) = a + b + n * (b + c)；即 a=(n - 1) * b + n * c = (n - 1)(b + c) +c a+b 为慢指针走的步数，则2*(a+b)为快指针走的步数，b+c为环的长度注意到b+c恰好为环的长度，故可以推出，如将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。 故两指针会在环开始位置相遇。

代码

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

参考文献

​​[编程题]linked-list-cycle-ii​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。