链表中的环

问题:给定一个单向链表,如何判断链表中是否有环?

思考

兔子和乌龟要进行一次赛跑 ,他们将在跑道同一位置同时起跑:

  1. 如果在直线跑道上  比赛,那么兔子和乌龟最终会分别跑到终点;
  2. 如果在圆形跑道上比赛,因为兔子的速度比乌龟快,所以兔子最终会赶上乌龟 。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const hasCycle = function(head) {
// 如果头节点不存在,或者链表只有头节点,则链表没有环
if(head === null || head.next === null){
return false;
}

// 慢指针每次移动一步,快指针每次移动两步
let slow = head.next;
let fast = head.next.next;

// 快指针已经到达终点,说明链表没有环
if(fast === null){
return false;
}

// 每移动一次就检查一遍两个指针是否相遇
while(slow!==fast){
// 如果快指针下一步可以到达终点,说明链表没有环
if(fast.next === null || fast.next.next === null){
return false;
}

// 慢指针向前走一步,快指针向前走两步
slow = slow.next;
fast = fast.next.next;
}

// 两个指针相遇,说明链表有环
return true;
};

新问题:对于有环单向链表,如何找到的  环的  起点。

思考 

判断链表是否有环的逻辑和上面一样,现在只关注  有环的情况。

假设:

  • 经过k步之后两个指针相遇,
  • 链表头节点到环的起点的距离为s,
  • 环的起到到相遇点的距离为m,
  • 环的长度为L


此时:
 慢指针走过的路程为:
Dslow = k = s + m + n1 * L (n1为慢指针绕环的次数)

快指针走过的路程为:
Dfast = 2k = s + m + n2 * L (n2为快指针绕环的次数)

合并得到s的表达式: s = (n2 - 2n1) * L - m

结论

当两个指针相遇时,将其中一个移动到头节点,然后让两个指针一步一步往后走,它们再次相遇的节点就是环起点。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @param {ListNode} head
* @return {ListNode}
*/
const detectCycle = function(head) {
if (!head) return null;
let slow = head;
let fast = head;
let cycle = false;

while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
cycle = true;
break;
}
}

if (cycle) {
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}

return null;
};