计算链表中环的长度
[!Tip]
本节源代码见Github链接🔗
问题描述
判定给定的链表是以NULL结尾,还是形成一个环。如果链表中存在环,返回环的长度
核心思路
通过Floyd环判定算法🔗来解决。主要包含以下4步:
- 定义两个指向链表头结点的指针slowPtr和fastPtr;
- 将两个指针按照不同的速度进行移动,如slowPtr每次向后移动1个结点,fastPtr每次向后移动2个结点;
- 若链表中存在环,slowPtr和fastPtr终将指向同一结点;若不存在环,fastPtr会先指向NULL;
- 确定存在环后,fastPtr停止不动,slowPtr继续移动,当两个指针再次相遇时,slowPtr移动的结点数即环的长度
实现代码
【👉🏻>>点击展开查看代码】
/**
* 计算链表中环的长度
*
* @author: Max Solider
* @date: 2022/10/9 14:18
* @param headNode
* @return int
*/
int findLoopLength(NormalListNode headNode) {
if (headNode == null || headNode.getNext() == null) {
return 0;
}
NormalListNode slowPtr = headNode, fastPtr = headNode;
boolean loopExists = false;
while (fastPtr.getNext() != null && fastPtr.getNext().getNext() != null) {
fastPtr = fastPtr.getNext().getNext();
slowPtr = slowPtr.getNext();
if (slowPtr == fastPtr) {
System.out.println("There is a loop in the linked list.");
loopExists = true;
break; }
}
if (!loopExists) {
System.out.println("There is no loop in the linked list.");
return 0;
}
int loopLength = 1;
slowPtr = slowPtr.getNext();
while (slowPtr != fastPtr) {
slowPtr = slowPtr.getNext();
loopLength++;
}
System.out.println("The loop in the linked list has " + loopLength + " nodes");
return loopLength;
}
时间复杂度
时间复杂度为O(n),用于遍历环。
空间复杂度
空间复杂度为O(1),用于存储临时变量。