142. Linked List Cycle II
2018-01-18 本文已影响269人
Rotten_Pencil
题目：
- Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
- 译文：给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回null。
知识点
- Linked List Cycle I —— 通过快慢两个指针来确定链表上是否存在环
- 快慢指针的相遇点到环入口点的距离 = 链表起始点到环入口点的距离
扩展点
- 快慢指针一直到相遇时的循环次数等于环的长度
循环次数 = 环的长度
- Case 1：一个完美的环状链表，即，链表的头尾相连
一个环形链表：{A，B，C，A，B，C，……}
其上存在两个指针，A指针移动速度是B指针的两倍。
A，B同时从节点1出发，所经过的节点如下：
快指针A：A->C->B->A
慢指针B：A->B->C->A
A、B指针在节点A第一次相遇，循环次数为3，而环的程度正好也为3。那这个是不是巧合呢？
首先我们要理解的是循环的次数代表的是什么。
1. 每次循环，对于B这个慢指针来说，意味着走了一个单位长度。
2. 而对于A来说，走了两个单位长度。
3. 那么二者第一次相遇必然是在A走了2圈，B走了1圈的时候。
4. 假如A的速度是B的3倍，那么二者第一次相遇是在A走了3圈，B走了1圈的时候。
5. 同理A是B的5倍速度，相遇时A走了5圈，B走了1圈
...
n. A的速度是B的n倍，相遇时A走了n圈，B走了1圈
从上面的观察我们可以发现，无论A的速度是B的几倍，两者第一次相遇必然是在B走了1圈时。
因为B的速度代表的是链表基本的长度单位，即从一个节点移动到下一个节点的距离。
同时在链表中，每个节点与节点之间这个距离是不变的。
当循环结束时，B走了1圈，正好是环的长度。而B每次移动一个单位距离，因此环的长度等于循环次数。
-
Case 2：不完美的环状链表，即，链表中某一中间节点与尾部相连
不完美的环形链表
一个环形链表（如图所示）：{D，E，A，B，C，A，B，C，……}
其上存在两个指针，A指针移动速度是B指针的两倍。
A，B同时从节点1出发，所经过的节点如下：
快指针A：D->A->C->B
慢指针B：D->E->A->B
根据上图，我们可以计算出A、B行走的距离：
A = d+e+a+b+c+a
B = d+e+a
因为A的速度是B的2倍，那么A行走的距离也因该是B的2倍：
d+e+a+b+c+a = 2(d+e+a)
a+b+c = d+e+a
从上图可以看出，a+b+c正好是环的长度，而d+e+a则是B行进的距离。
又知，每次循环B移动一个单位距离，因此在不完美的环状表中，循环次数亦是等于环的长度。
相遇点到环入口点的距离 = 链表起始点到环入口点的距离
根据上文公式，我们可以继续推导，即：
a+b+c = d+e+a
b+c = d+e
b+c是相遇点到环入口的距离
d+e是链表起点到环入口的距离
解题思路
- 先由快慢指针检测链表上是否存在环
- 如果环存在，根据相遇点到环入口点的距离 = 链表起始点到环入口点的距离，我们可以同时从D点（链表起始点）和B点（相遇点）循环两个指针
- 两个会最终指向A点，即，环的起始点
/**
* 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 *fast = head;
ListNode *slow = head;
while(fast != NULL && fast->next!=NULL){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){ //快慢指针相遇，说明环存在
//first代表着链表的起始点
//slow代表着相遇点
ListNode *first = head;
while(first != slow){//从相遇点和链表起始点同时循环两个指针，直到二者相遇，相遇点就是环起始点
first = first->next;
slow = slow->next;
}
return first;
}
}
return NULL;
}
};
