image.png
思路
快慢指针解法
- 定义两个指针
fast和slow, 每次让fast走两步, slow走一步, 当fast和slow相遇时,证明链表有环 -
如果求环的入口节点呢
image.png - 假设链表
头节点到环的入口要走x步, 环入口到 fast和slow相遇的点位y, 相遇点y到环入口为z - 可以推到出如下公式 slow 到相遇点 = x + y, fast到相遇点= x + y + n(y + z) ,
n(y + z) 表示fast在环内多跑的若干圈数 - fast是slow的两倍速度 2(x + y) = x + y + n(y + z)
- 两边抵消掉一个 (x + y) 得结果
x + y = n (y + z) - 需要找到环形的入口, 就是我们求的是x的值, 将x单独放到左边
x = n(y + z) - y; -
y + z表示理解为走一圈需要多少步 - 从n(y + z) 分出一个 y + z来, 即分离出一圈来, 整理后的公式: x = (n-1) (y + z) + z
这里注意n一定是大于等于1
因为 fast至少要走一圈才能和slow相遇, 这里还可以理解为无论fast在环内走几圈都一样, 假设n =1(一圈) n(y + z) = 1 * (y + z ) = y + z
x = (n-1) (y + z) + z 上面的公式就化解为 x = z; 所以求出z的值即可 - 定义两个指针index1 = head 指向头节点, index2 = slow 指向相遇节点y, 同时向前每次走一步,
当index1 和 index2相遇时, 就是z的值, 即环形链表入口的节点
public static ListNode detectCycle1(ListNode head) {
ListNode fast, slow;
fast = head;
slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
ListNode index1 = head;
ListNode index2 = slow;
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
