怎么做才能让网站快速收录,长沙制作公司宣传片哪家好,种子搜索引擎,网站建设和销售有关吗链表中环的入口节点 描述 链表中环的入口节点 给一个长度为n链表#xff0c;若其中包含环#xff0c;请找出该链表的环的入口结点#xff0c;否则#xff0c;返回null。
数据范围#xff1a; n≤10000#xff0c; 1结点值10000 要求#xff1a;空间复杂度 O(1)… 链表中环的入口节点 描述 链表中环的入口节点 给一个长度为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 NodeV {public NodeV pre;public NodeV 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 NodeInteger entryNodeOfLoop(NodeInteger head) {if (head null || head.next null){return null;}NodeInteger fast head;NodeInteger 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(YZ)Z n0n为环的圈数的结论成立为证明A到B走和C到B顺时针相同速度走第一次相遇的点一定为B点
即证明X n(YZ)Z n0n为环的圈数由第一次相遇在C点得2(XY) X w(YZ) Y;(w1w为环的圈数)
推导 2(XY) X w(YZ) Y Z Y;(w0w为环的圈数) 2(XY) X w(YZ) 2Y Z;(w0w为环的圈数) X w(YZ) Z ;(w0w为环的圈数)所以X n(YZ)Z n0n为环的圈数。成立即A到B走和C到B顺时针相同速度走第一次相遇的点一定为B点。
