青岛外贸假发网站建设,seo优化名词解释,企业网站建设管理及推广,什么科技网站建设题目
给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内部使…题目
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1 输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。
代码
static public ListNode hasCycle_StartNode(ListNode head) {ListNode slow head, fast head; // 将 fast 的起始位置设置为 headwhile (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {// 此时slow和fast在环的中相遇但是相遇的点不一定是环的入口点因为进入指针环的时机是不一样的ListNode cycle head;// 重置一个新节点走a的距离就可以和slow后续的移动汇合且一定是环开始的节点while (cycle ! slow) {cycle cycle.next;slow slow.next;}return cycle;}}return null;
}总结
a从链表头到环的起始节点的距离。 b从环的起始节点到快慢指针相遇点的距离。 c环的长度。
慢指针 slow 从头节点开始走了 a b 的距离到达相遇点。 快指针 fast 从头节点开始走了 a b n*c 的距离其中 n 是快指针在环内绕的圈数。 当快慢指针相遇时有以下关系
slow 走的距离a bfast 走的距离a b n*c
由于快指针的速度是慢指针的两倍得出 2(a b) a b nc a b nc 这表明慢指针走的距离ab是环长度的整数倍
