wordpress lampp建站,定制app开发软件,注册安全工程师白考了,成都网络关键词排名给定一个链表#xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。
为了表示给定链表中的环#xff0c;我们使用整数 pos 来表示链表尾连接到链表中的位置#xff08;索引从 0 开始#xff09;。 如果 pos 是 -1#xff0c;则在该链表中没有…给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 null。
为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。
说明不允许修改给定的链表。 示例 1
输入head [3,2,0,-4], pos 1 输出tail connects to node index 1 解释链表中有一个环其尾部连接到第二个节点。 示例 2
输入head [1,2], pos 0 输出tail connects to node index 0 解释链表中有一个环其尾部连接到第一个节点。 示例 3
输入head [1], pos -1 输出no cycle 解释链表中没有环。 思路从环形链表那道题来看当两个指针在环内相遇时快指针比慢指针多走了n步设环周长为k
则n%k0
慢指针总共走了n步设环外的长度为m则它在环内走了n-m步因此它再走m步就到达了环的入口处
所以我们让一个指针从起点开始走当它与慢指针相遇时它们都走了m步相遇的地点就是入口
提交的代码
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if(headnull||head.nextnull) { return null; } ListNode slow,fast; slow head; fast head.next; while(slow!fast) { if(fast.nextnull||fast.next.nextnull) { return null; } slow slow.next; fast fast.next.next; } slow slow.next; // System.out.println(head.val); fast head; while(fast!slow) { fast fast.next; slow slow.next; // System.out.println(fast.val slow.val); } return fast; } }
