莲湖免费做网站,模板网生产线,营销号是啥意思,企业家网站建设一、题目描述
给定一个链表的头节点 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 的链表节点
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出返回索引为 0 的链表节点
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出返回 null
解释链表中没有环。提示
链表中节点的数目范围在范围 [0, 10^4] 内-10^5 Node.val 10^5pos 的值为 -1 或者链表中的一个有效索引
二、解题思路
这个问题是著名的“链表环入口”问题可以使用“快慢指针”的解法来解决。以下是详细的解题步骤 初始化两个指针一个快指针fast和一个慢指针slow它们都从链表的头节点开始移动。 移动快慢指针快指针每次移动两步慢指针每次移动一步。 检查是否有环如果快指针和慢指针相遇则说明链表存在环。 寻找环的入口当快慢指针相遇后将其中一个指针例如慢指针移动到链表的头节点另一个指针保持在相遇点。然后两个指针以相同的速度移动当它们再次相遇时所在的位置就是环的入口。 返回结果如果链表无环则返回 null如果有环则返回环的入口节点。
三、具体代码
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head;ListNode slow head;boolean hasCycle false;// 检查是否有环while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if (fast slow) {hasCycle true;break;}}// 如果没有环返回 nullif (!hasCycle) {return null;}// 寻找环的入口slow head;while (slow ! fast) {slow slow.next;fast fast.next;}return slow; // 返回环的入口节点}
}四、时间复杂度和空间复杂度
1. 时间复杂度 检查是否有环的阶段 初始化两个指针一个快指针每次移动两步和一个慢指针每次移动一步。假设链表总长度为 L非环部分长度为 a环部分长度为 b。在没有遇到环的情况下快指针和慢指针最多移动 L 步即 L a b。当快慢指针都进入环中后它们会在环中相遇。设它们在环中相遇前快指针比慢指针多走了 n 步则有 n b。快慢指针相遇时它们分别走了 a b 和 a b - n 步即快指针走了 L 步慢指针走了 L - n 步。由于快指针走的步数是慢指针的两倍所以有 2(L - n) L解得 n L/2。因此慢指针在环中走了 L/2 步快指针走了 L 步它们相遇的时间复杂度为 O(L)。 寻找环的入口的阶段 将慢指针移回链表头部快指针保持在相遇点。由于慢指针在环中已经走了 L/2 步且快指针在相遇点所以它们相遇时慢指针走了 a 步快指针走了 a b 步。因此它们相遇的时间复杂度为 O(a)。
综上所述总的时间复杂度为 O(L)。
2. 空间复杂度
该算法只使用了几个指针变量没有使用额外的数据结构。因此空间复杂度为 O(1)。
五、总结知识点 链表操作代码中涉及到链表的基本操作包括遍历链表、判断节点是否为空、移动指针等。 快慢指针技巧这是解决链表相关问题的一种常用技巧通过设置两个指针一个快一个慢来解决问题。在本题中快指针每次移动两步慢指针每次移动一步用于检测链表中是否存在环。 循环检测通过快慢指针的相遇来判断链表中是否存在环。如果快慢指针相遇则说明链表中有环如果快指针遇到空节点则说明链表中无环。 数学推理当快慢指针在环中相遇时通过数学推理可以得出慢指针走过的距离和环的入口之间的关系从而找到环的入口。 边界条件处理代码中需要处理链表为空或者链表没有环的情况这需要仔细考虑边界条件确保代码的鲁棒性。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
