本文主要是介绍链表中环的入口节点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
链表中环的入口节点
描述
链表中环的入口节点
给一个长度为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点。
这篇关于链表中环的入口节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!