如何判断一个单向链表是否有环？

自问
数据结构, 算法

算法不精也不熟，最先想到的总是最笨的方法，遍历，时间复杂度为 O(n2)。

后来 Google 一番，找到了 O(n) 的解决方案，很聪明（但也有种怎么也想不出来的感觉:cry:）。这个问题还有几个相关的问题：

  1. 如何判断一个单向链表是否有环？
  2. 若有，环的入口在何方？
  3. 最后，环的长度与该单向链表的长度各是多少？

借记录故，我来各自解答一番。

如何判断一个单向链表是否有环

一个单向链表如下，使用两个指针，一快（二倍速）一慢遍历该链表，在链表有环的情况下，它们总会相遇的。快指针总会追上慢指针，就像跑步一样。因此，若相遇，则有环；反之，快指针会跑到链表尾（null）。

环的入口

假设链表长度为 n，入口在 m 处，环长度为 L。假设目前已经过 t 次循环，快指针走过路程为 2t，慢指针走过路程为 t。很容易想到，在极限状况下（首尾相连），相遇点总是在链表起点（此时 t = n），所以总能保证相遇时 t <= n，也就是慢指针尚未遍历完链表，而快指针已经绕环 r（r >= 1）圈了。

根据这些相互关系，我们可以得出算式：

2t = t + Lr
t = Lr

假设相遇点与碰撞点距离为 x，有：

x + m = t = Lr = L * (r - 1) + L
x = L - m
m = L - x

即起点至入口的距离为相遇点继续走到入口的距离。（也就是图中蓝色与青色的部分）

借助此特性，于起点与 x （相遇点）各设一个一倍速指针，它们会在 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
function Node(value) {
  this.value = value
  this.next = null
}
let oList = new Node(1)
let count = 1, tail = oList
// 之前我想用 top = oList，但浏览器报错，说 top 已经定义过。
// window 有 top / self / parent 属性，其含义暂略
// 我尝试给这三者赋值，只有 top 会报错，什么鬼:joy:
while (count < 6) {
  tail.next = new Node(++count)
  tail = tail.next
}
tail.next = oList.next.next
// 判断是否有环
function isCircular(head) {
  let slow = head, fast = head
  
  while (fast) {
    fast = fast.next
    if (!fast) return false
    else fast = fast.next
    slow = slow.next
    if (slow === fast) return true
  }
  return false
}
// 找到入口点
function getEntrance(head) {
  let slow = head, fast = head, meet = null
  while (fast) {
    fast = fast.next
    if (!fast) return null
    fast = fast.next
    slow = slow.next
    if (slow === fast) {
      meet = slow
      break
    }
  }
  if (!fast) return null
  slow = head
  while (slow !== meet) {
    slow = slow.next
    meet = meet.next
  }
  return meet
}
function getCircleLength(head) {
  let entry = getEntrance(head)
  let iterator = entry
  let ret = 0
  do {
    iterator = iterator.next
    ret++
  } while (iterator !== entry)
  return ret
}
function getListLength(head) {
  let entry = getEntrance(head)
  let iterator = head
  let ret = 0
  do {
    iterator = iterator.next
    ret++
  } while (iterator !== entry)
  return ret + getCircleLength(head)
}
if (isCircular(oList)) {
  console.log(getEntrance(oList))     // Node { value: 3, next: [Object] }
  console.log(getCircleLength(oList)) // 4
  console.log(getListLength(oList))   // 6
}

参考资料

  1. 判断单链表是否存在环及求环入口点
Comments