Linked List Cycle II

时间：2014-03-06 08:12:07 阅读：442 评论：0 收藏：0 [点我收藏+]

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?

1. 快慢指针判断是否有环，无环则直接退出；
2. 如果有有环，这是lo和hi都指向一个节点A，为了得到环的入口节点（记为B)，分析如下（对环长小于head到入口点情况，从取余的脚看和下边分析是一样的）：
a. 假设从head到环入口节点(B）共需移动n步，则lo到B时，A已经移动的2n步(记为节点C)，所以从入口B到当前hi的位置（C)的长度就等于从头节点到入口的长度（从对环长度取余来看总是正确的).
b. 示意图大概是这样 B --(l1)-- C --(l2)--- B, l1和l2表示从B顺序到C的长度和从C顺序再到B的长度（因为是一个环嘛),这是lo就是B点，hi就是C点
c. hi为了追上lo，每次移动能缩短一步距离，现在hi距离lo可以认为是l2；
d. 所以lo移动到B + l2（节点D)的时候，hi追上了lo；
e. 所以这个时候D到B是l1长，一个指针从head出发，一个从D出发，步长一样，它们会在入口点B相会

------------------------------

/**
* 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 == NULL || head->next == NULL) return NULL;
ListNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}

if (fast != slow) return NULL;
slow = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}

return fast;
}
};

Linked List Cycle II,布布扣,bubuko.com

Linked List Cycle II

原文：http://blog.csdn.net/icomputational/article/details/20577957

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)