nat123做网站 查封,服务行业做网站,wordpress内部服务器错误,微信开发者工具如何使用给定一个链表#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 解释链表中没有环。 思路
慢指针一次一步快指针一次两步。能相遇就是有环反之没有环。
让一个指针从头走另一个从相遇点开始走然后再次相遇的地方就是入环点不明白的画一画想一想操场跑步就明白了。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {private ListNode getIntersect(ListNode head) {ListNode tortoise head;ListNode hare head;while (hare ! null hare.next ! null) {tortoise tortoise.next;hare hare.next.next;if (tortoise hare) {return tortoise;}}return null;
}public ListNode detectCycle(ListNode head) {if (head null) {return null;}ListNode intersect getIntersect(head);if (intersect null) return null;ListNode ptr1 head;ListNode ptr2 intersect;while (ptr1 ! ptr2) {ptr1 ptr1.next;ptr2 ptr2.next;}return ptr1;}
}
