算法不精也不熟,最先想到的总是最笨的方法,遍历,时间复杂度为 O(n2 )。
后来 Google 一番,找到了 O(n) 的解决方案,很聪明(但也有种怎么也想不出来的感觉:cry:)。这个问题还有几个相关的问题:
如何判断一个单向链表是否有环?
若有,环的入口在何方?
最后,环的长度与该单向链表的长度各是多少?
借记录故,我来各自解答一番。
如何判断一个单向链表是否有环 一个单向链表如下,使用两个指针,一快(二倍速)一慢遍历该链表,在链表有环的情况下,它们总会相遇的。快指针总会追上慢指针,就像跑步一样。因此,若相遇,则有环;反之,快指针会跑到链表尾(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
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))
console .log(getCircleLength(oList))
console .log(getListLength(oList))
}
参考资料
判断单链表是否存在环及求环入口点