如何判断一个链表是否有环?如果有环,如何查找入环点?
如何判断一个链表是否有环?如果有环,如何查找入环点?
有环链表:
无环链表:
两者的区别在于是否有尾节点和相交节点.
以是否有相交节点为突破口,这里介绍两种方法:
1. 哈希表
对每个遍历过的节点进行记录,如果遍历到空节点,说明链表是无环链表;如果节点已记录过就说明链表是有环链表,这个节点就是链表的入环点.
复杂度分析:
时间复杂度:O(N),只对链表做一次全遍历就可以确定;
空间复杂度:O(N),需要额外建立一个哈希表对链表节点进行存储.
2. 快慢指针
快慢指针的思路是,2人在操场跑步,跑的快的人在若干圈后一定会追上跑的慢的人.
根据这个思路,创建快慢两个指针,快指针,每次移动2个节点;慢指针,每次移动1个节点;如果两个指针有相交,则说明链表是有环链表,并且快指针的移动距离是慢指针的2倍.
快慢指针的移动轨迹参考下图,偏移4次的慢指针和偏移8次的快指针在节点5处相遇,链表是有环链表.
那入环点怎么判断呢?
我们再用平面几何的形式看下快慢指针的移动轨迹.
H: 链表头 A: 入环点 B: 快慢指针相交点
先做如下约定:
LHA: 链表头H到入环点A的距离;
LAB: 链表节点A顺时针到节点B的距离;
LBA: 链表节点B顺时针到节点A的距离;
根据移动距离,可知:
2*慢指针移动距离 = 快指针移动距离
2*(LHA + LAB) = LHA + LAB + LBA + LAB;
最后推导出
LHA = LBA
所以,只要从相交点和头节点同时遍历到的相同节点就能找到入环点.
总结一下,使用快慢指针的方式,虽然会比哈希表的方式多遍历一些节点,但遍历次数是有限的,并且是线性增加的,所以时间复杂度是O(N);快慢指针算法只需要两个指针,需要的空间也是常数级的,所以空间复杂度是O(1);
附上代码:
代码语言：javascript复制public class CycleListNode {
/**
* 快慢指针
*/
public static boolean hasCycleByPoint(ListNode head) {
boolean hasCycle = true;
ListNode fastIndex = head;
ListNode slowIndex = head;
do {
if (fastIndex == null) {
hasCycle = false;
break;
}
if (fastIndex.next == null) {
hasCycle = false;
break;
}
fastIndex = fastIndex.next.next;
slowIndex = slowIndex.next;
} while (fastIndex != slowIndex);
return hasCycle;
}
/**
* 环形相加点
* F:头结点到入环结点距离
* B:入环结点到快慢指针相交结点距离
* C:快慢指针相交结点到入环结点距离
* 2*慢指针移动距离=快指针移动距离
* 2(F+B)=F+B+B+C
* F = C
*
* @param head
* @return
*/
static ListNode getEntranceNode(ListNode head) {
ListNode fastIndex = head;
ListNode slowIndex = head;
do {
if (fastIndex == null) {
break;
}
if (fastIndex.next == null) {
fastIndex = fastIndex.next;
break;
}
fastIndex = fastIndex.next.next;
slowIndex = slowIndex.next;
} while (fastIndex != slowIndex);
if (fastIndex == null) {
return null;
}
ListNode headIndex = head;
while (fastIndex != headIndex) {
fastIndex = fastIndex.next;
headIndex = headIndex.next;
}
return fastIndex;
}
/**
* hash
*/
public static boolean hasCycleByHash(ListNode head) {
boolean hasCycle = false;
Set set = new HashSet();
while (head != null) {
if (set.contains(head)) {
hasCycle = true;
break;
}
set.add(head);
head = head.next;
}
return hasCycle;
}
public static void main(String[] args) {
test1();
test2();
}
private static void test1() {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n2;
Assert.assertTrue(hasCycleByPoint(n1));
Assert.assertEquals(2, getEntranceNode(n1).val);
}
private static void test2() {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
Assert.assertFalse(hasCycleByPoint(n1));
Assert.assertNull(getEntranceNode(n1));
}
static class ListNode {
int val;
ListNode next;
public ListNode(int data) {
this.val = data;
}
}
}