leetcode-142-Linked List Cycle II

问题

题目：[leetcode-142]

思路

寻找环的入口，需要做如下的数学证明。先给出示意图如下：

做如下假设：

设直线段的端点为 O点 环的入口点为 A点 快慢指针相遇的点为 B点 其中，有 OA−→−=l,AB−→−=r0BC−→−=c,

当快慢指针相遇时，有下面的式子：

dlow=l+r0(1) dfast=l+k⋅r+r0，其中r是环的周长(2) 由于快指针走过的路程是慢指针的两倍，所以有： 2⋅(l+r0)=l+k⋅r+r0(3) 整理得： l=k⋅r−r0(4) 即 l=(k−1)⋅r+c(5) 所以，相遇点到入口的距离等于端点到入口的距离。 所以，分别设两个指针从端点和相遇点开始移动，当他们相遇时，即为环的入口。

代码

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