这是一题常见的面试题，考察求职者对链表的理解，题目在leetcode上：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
首先来判断链表有没有环。看一个直观的例子：假设小明和专业运动员在400米标准环形操场上比赛跑步，由于长久缺乏锻炼，小明匀速跑一圈需要2分钟，而运动员匀速跑一圈只要1分钟。那么如果两个人同时、同一点出发，1分钟后小明跑了半圈，而运动员已经跑完一圈，开始第二圈；2分钟时，小明终于跑完一圈，而运动员刚好跑完第二圈，整整比小明多跑一圈，两人在终点相遇。如果运动员在小明前方S米处和小明同时出发，那么运动员会在小明跑完一圈前就追上小明（可怜的小明）。
回归问题，如果我们设定两个指针p1、p2，开始时指在链表头head，p1代表小明，每次前进一步；p2代表运动员，每次前进两步。如下图环形链表中，6步之后p2追上p1，再次相遇。
环链表
对于一般链表，p1、p2仍然同时从表头A点出发，由于前面有段非环的直线路程，当p1到B点进入环的时刻，p2已经在环内跑了一段路了，此刻开始，类似运动员和小明同时出发，而运动员的出发点领先于小明，在不超过一圈的路程内，运动员能够追上小明，p2也能在一圈以内赶上p1，假设两指针在C点相遇，此时，p1==p2，利用这个条件，我们可以断定链表有环。否则，当运动员跑到了尽头，还没有和小明相遇，说明他们的跑道没有环。
一般链表
再来看看环的入口在哪里。我们利用p1、p2在C点相遇的时刻来分析，假设AB的距离为s，BC的距离为r，CB的距离为l，p1走过距离为a = s + r则可以有以下关系：
(1)总长度 = s + r + l;
(2)环的长度 = r + l;
(3)p2走过距离 = 2a;
(4)p2 - p1 = a = s + r;
相遇时，p2比p1在环内多走了n圈(n>=1):
(5) p2 - p1 = n(r + l)；
结合(4)、(5): n(r + l) = s + r;
nr - r = s - nl;
(n - 1)r = s - (n - 1)l -l;
(6) (n -1)(r + l) = s - l;
从（6）我们可以看出一些规律（注意：环的长度 = r + l），当n = 1时，说明p2比p1多跑了一圈，此时，s = l。当n > 1时，说明p2比p1多跑了整整(n -1)圈再相遇，考虑s - l为环长度的(n -1)倍，(n -1)(r + l) + l = s，说明如果一个节点从A点开始，走s的距离和从C点开始走(n -1)圈再多l的距离刚好又能相遇在B点，B也正是环的入口。
分析完毕，再上C++代码：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *detectCycle(ListNode *head) {
ListNode *p1 = head, *p2 = head;
bool hasCycle = false;
// 特殊情况判断
if(head == NULL)
return NULL;
// p2走得快，当p2->next == NULL时，说明没有环
while(p2 && p2->next)
{
p1 = p1->next;
p2 = p2->next->next;
if(p1 == p2)
{
// 有环，立下flag
hasCycle = true;
break;
}
}
if(!hasCycle)
{
return NULL;
}
// 一个从A前进，一个从C前进
p2 = head;
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
网友评论