带环单链表

链表一直是非常重要的数据结构,相关问题经常会被问到;本文将介绍与单链表环有关的问题…

如何判断单链表是否存在环

如果单链表的尾节点的next指针不为null,而指向链表中的某个节点,则称该单链表存在环。

比如下图所示的单链表是一个存在环的单链表(请暂时忽略meeting):

判断单链表是否存在环有多种方法,比如你可以使用哈希缓存,快慢指针甚至直接暴力的遍历等方法。本文介绍快慢指针法的解决策略。

快慢指针法的实现思路如下:

  1. 定义两个指针:快指针和慢指针;都指向第一个节点
  2. 快指针一次向后移动一个节点,慢指针一次向后移动两个节点
  3. 如果快慢指针最终指向同一个节点并且快慢指针均不为空,说明存在环

整个过程如下图所示(假设黄色圆代表慢指针,蓝色圆代码快指针):

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isExistLoop(SinglyList list) {
if(list.head==null||list.head.next==null) {
return false;
}
SinglyNode<T> fast=list.head.next;
SinglyNode<T> slow=list.head.next;
while(slow!=null&&fast.next!=null) {
slow=slow.next;
fast=fast.next.next;
if(slow==fast) {
return true;
}
}
return false;
}

如何得到环入口

还是以上面的单链表为例:

根据快慢指针的判断方法,最终快慢指针会相遇在某一个节点,假设这个节点就是meeting(节点7)

由于fast指针的速度是slow的两倍,所以当fast和slow首次相遇时,假设slow经过结点数为S,fast经过的结点数为2S;这是一个前提以知条件。
假设环入口(3)到首节点间的结点数为A,环入口到meeting结点的结点数为B,环的长度为R,易知:
S=A+B
2S=A+B+N*R(N为fast已经循环的圈数,该例中N=1)
解得:S=N*R(S=R);表明slow走过的长度即为环长的整数倍

假设链表的长度为L
A+B=S=NR=(N-1)R+R=(N-1)R+L-A
解得A=(N-1)
R+L-A-B
这说明如果当快慢指针相遇时,meeting到环入口的距离=头节点到环入口的距离

综上所示,得到环的入口节点的思路如下(你完全可以只关注接下来的总结,上面的推理只是帮助理解):
如果存在环

  1. 找到快慢指针相遇的节点meeting
  2. 定义一个指针指向第一个节点,另一个指针指向meeting
  3. 两个指针同时向后移动直到两个指针相等
  4. 此时两个指针都指向入口的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
public SinglyNode<T> getEntryOfLoop(SinglyList<T> list) {
SinglyNode<T> meeting=getMeetingNode(list);
if(meeting==null) {
return null;
}
SinglyNode<T> first=list.head.next;
SinglyNode<T> second=meeting;
while(first!=second) {
first=first.next;
second=second.next;
}
return first;
}

计算环的长度

根据上面的分析,计算环长的思路是:

  1. 从快慢指针第一次相遇的节点处开始同时向后移动
  2. 移动一次长度加1
  3. 当两个指针再次相遇时,计算得到环的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int getLengthOfLoop(SinglyList<T> list) {
if(list.head==null||list.head.next==null) {
return -1;
}
SinglyNode<T> fast=list.head.next;
SinglyNode<T> slow=list.head.next;
while(fast!=null&&slow!=null) {
slow=slow.next;
fast=fast.next.next;
if(slow==fast) {
break; //此时fast和slow第一次相遇
}
}
int len=1;
slow=slow.next;
fast=fast.next.next;
while(slow!=fast) {
slow=slow.next;
fast=fast.next.next;
len++;
}
return len;
}

好了,仔细思考这次的环问题,其实并不难理解,今天就介绍到这里了!

smartpig wechat
扫一扫关注微信公众号
0%