LeetCode-142. Linked List Cycle II

LeetCode-142. Linked List Cycle II

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.

题解：

使用快慢指针找到环内相遇点，然后头结点和环内相遇点到入环点的距离为环长度的倍数，一直寻找即可。

class Solution {public: ListNode *detectCycle(ListNode *head) { if (head == NULL || head->next == NULL) { return NULL; } bool loop = false; ListNode *p = head, *q = head; while (q != NULL && q->next != NULL) { p = p->next; q = q->next->next; if (p == q) { loop = true; break; } } if (loop == true) { q = head; while (q != p) { q = q->next; p = p->next; } return p; } return NULL; }};

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