找到链表中环的起始点
[!Tip]
本节源代码见Github链接🔗
问题描述
判定给定的链表是以NULL结尾，还是形成一个环。如果链表中存在环，找到环的起始结点
核心思路
根据对前面03-判定链表中是否存在环和04-计算链表中环的长度两个问题的解决经验，本节问题仍然可以通过Floyd环判定算法🔗来解决。
假设链表起始点为S，环的起点是P，两个指针的首次相遇点是M，并假设S到P的距离是x，P到M的距离是y，环的长度是z。当两个指针slowPtr和fastPtr相遇时，我们可以推导出以下结论：
- slowPtr移动的距离是：
s = x + y + n * z (n代表slowPtr走过的环的圈数) - 由于fastPtr的移动速度是slowPtr移速的两倍，因此fastPtr移动的距离2s。但fastPtr只在环上比slowPtr多移动了部分距离，因此：
2s = 2(x + y + n * z) = x + y + m * z (n,m 分别代表slowPtr和fastPtr走过的环的圈数) - 由上述等式相减可知：
s = (m - n) * z = x + y + n * z (n,m 分别代表slowPtr和fastPtr走过的环的圈数) - 由此可知，当两个指针相遇时，slowPtr的移动距离是整数倍环的长度，链表头到相遇点的距离(即x + y)也是整数倍环的长度；
- 综上所述，环起点距离两个指针的相遇点的距离为y，由于x + y是环长度的整数倍，若从相遇点再往前移动x个结点，移动后到达环起点。
综上，找到链表中环的起始结点，主要包含以下4步：
- 定义两个指向链表头结点的指针slowPtr和fastPtr；
- 将两个指针按照不同的速度进行移动，如slowPtr每次向后移动1个结点，fastPtr每次向后移动2个结点；
- 若链表中存在环，slowPtr和fastPtr终将指向同一结点；若不存在环，fastPtr会先指向NULL；
- 确定存在环后，slowPtr回到链表起点，然后将slowPtr和fastPtr两个指针按相同的速度进行移动，每次移动1个结点。当两个指针再次相遇时，相遇点即环起点。
实现代码
【👉🏻>>点击展开查看代码】
/**
* 找到链表中环的起点
*
* @author: Max Solider
* @date: 2022/10/9 14:18
* @param headNode
* @return NormalListNode
*/
NormalListNode findBeginofLoop(NormalListNode headNode) {
if (headNode == null || headNode.getNext() == null) {
System.out.println("There is no loop in the linked list.");
return null; }
// 判断是否存在环，找到首次相遇点
NormalListNode slowPtr = headNode, fastPtr = headNode;
boolean loopExists = false;
while (fastPtr.getNext() != null && fastPtr.getNext().getNext() != null) {
fastPtr = fastPtr.getNext().getNext();
slowPtr = slowPtr.getNext();
if (fastPtr == slowPtr) {
loopExists = true;
break; }
}
if (!loopExists) {
System.out.println("There is no loop in the linked list.");
return null; }
System.out.println("There is a loop in the linked list. The meeting node's value is :" + slowPtr.getData());
// 将slowPtr指向表头，然后两个指针按照相同速度向前移动，再次相遇点即环起点
slowPtr = headNode;
while (slowPtr != fastPtr) {
slowPtr = slowPtr.getNext();
fastPtr = fastPtr.getNext();
}
System.out.println("There begin node of loop is :" + slowPtr.getData());
return slowPtr;
}
时间复杂度
时间复杂度为O(n)，用于扫描长度为n的链表。
空间复杂度
空间复杂度为O(1)，用于存储临时变量。