当前位置：首页 > news >正文

链表中环的入口节点

news 来源：原创 2024/9/29 3:36:32

链表中环的入口节点

描述

链表中环的入口节点
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n≤10000， 1<=结点值<=10000
要求：空间复杂度 O(1)，时间复杂度 O(n)

解法一

解法一：有环的链表，在遍历时会在环中一直循环，想要获得环的入口结点，
直观地想，可以使用hash法保存出现的结点，当重复环的遍历过程时，第一次碰到重复的结点即为环入口结点B。

解法二

解法二：通过定义slow和fast指针，slow每走一步，fast走两步，若是有环，则一定会在环的某个结点处相遇（slow == fast），
根据下图分析计算，C为fast和slow指针第一次相遇的点。可知从C到B与从A到B以相同速度走第一次相遇的节点一定为B，即为入口点。解法二的实现，如下。
在这里插入图片描述

代码实现

public class Node<V> {public Node<V> pre;public Node<V> next;private V v;public Node(V v) {this.v = v;}public V getV() {return v;}public void setV(V v) {this.v = v;}
}
public static Node<Integer> entryNodeOfLoop(Node<Integer> head) {if (head == null || head.next == null){return null;}Node<Integer> fast = head;Node<Integer> slow = head;while (fast !=null && fast.next !=null){fast = fast.next.next;slow = slow.next;if (slow == fast){break;}}// 若是快指针指向null，则不存在环if(fast == null || fast.next == null)return null;// 重新指向链表头部fast = head;while (fast !=slow){fast = fast.next;slow = slow.next;}return fast;
}

从C到B与从A到B以相同速度走第一次相遇的节点一定为B？

在这里插入图片描述
我们用数学的方式证明一下。

如果结论：A到B走和C到B顺时针相同速度走，第一次相遇的点一定为B点。成立
那么数学表达式有 X = n(Y+Z)+Z  n>=0，n为环的圈数；的结论成立为证明A到B走和C到B顺时针相同速度走，第一次相遇的点一定为B点
即证明：X = n(Y+Z)+Z  n>=0；n为环的圈数由第一次相遇在C点得：2(X+Y) = X + w(Y+Z) + Y;(w>=1，w为环的圈数)
推导：==>  2(X+Y) = X + w(Y+Z) + Y + Z + Y;(w>=0，w为环的圈数)==>  2(X+Y) = X + w(Y+Z) + 2Y + Z;(w>=0，w为环的圈数)==>          X  = w(Y+Z) +Z ;(w>=0，w为环的圈数)所以：X = n(Y+Z)+Z  n>=0；n为环的圈数。成立即：A到B走和C到B顺时针相同速度走，第一次相遇的点一定为B点。