首页 > 代码库 > Leetcode: Linked List Cycle II
Leetcode: Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
分析：类似于linked list cycle I，用两个pointer，一个每个step往后移一个，另一个每个step往后移两个。当两个指针相交时，快指针走过的路程恰好是慢指针走过的路程的两倍，则我们可以得到：从链表头到环开始点的距离等于从两指针相交点到环开始点的距离（next方向）。那么我们让slow指针继续走，fast指针从head开始往后走（每个step后移一个），当fast和slow重合时即为环开始点。代码如下：
class Solution {public: ListNode *detectCycle(ListNode *head) { if(head == NULL || head->next == NULL) return NULL; ListNode *slow = head, *fast = head; //find meeting point while(slow->next && fast && fast->next){ slow = slow->next; fast = fast->next->next; if(slow == fast) break; } //no cycle if(slow != fast) return NULL; //find cycle beginning fast = head; while(fast != slow){ fast = fast->next; slow = slow->next; } return fast; }};
Leetcode: Linked List Cycle II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。