LeetCode-环形链表II
为找到入口点可以用以下方法
- 使用快慢指针法直到两个指针相遇
- 头节点处创建一个新的指针,并且向前移动,两个指针相遇处创建一个新的指针,并且向前移动,直到两个指针相遇为入口点
设 起点为A ,入口点为B,快慢指针相遇点为C
AB = n, BC = k,环长为m
因此快慢指针相遇时,快慢指针走过长度
快: n+am+k
慢: n+bm+k
因此有等式
n+am+k = 2(n+b*m+k)
化简后得到
n+k = (a-2b)*m ---{1}
由于从快慢指针处再出发与头指针同时出发,若要满足在入口相遇,则二者再次走的长度为n,因此
慢指针新长度:n+b*m+k
带入1式子得到
n+bm+k
= (a-b)m+n
显然这是一个环的长度倍数再加上AB长度,因此必定在出口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) return NULL;
ListNode * a = head;
ListNode * b = head;
while(true){
if(a->next == NULL || a->next->next == NULL || b->next == NULL){
return NULL;
}
a = a->next->next;
b = b->next;
if(a == b){
break;
}
}
ListNode *c = head;
while(a != c){
a=a->next;
c=c->next;
}
return c;
}
};