温州专业营销网站公司,网络建设规划,ui页面设计规范,婚礼视频制作软件题目链接#xff1a;https://leetcode.cn/problems/c32eOV/
1. 题目介绍#xff08;23. 链表中环的入口节点#xff09; 给定一个链表#xff0c;返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环#x…题目链接https://leetcode.cn/problems/c32eOV/
1. 题目介绍23. 链表中环的入口节点 给定一个链表返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环则返回 null。 为了表示给定链表中的环我们使用整数 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, 104] 内-105 Node.val 105pos 的值为 -1 或者链表中的一个有效索引 【跟踪】 进阶 是否可以使用 O(1) 空间解决此题 【相关题目】 注意 本题与主站 142. 环形链表 II 题目相同。 2. 题解
2.1 原书题解快慢指针-- O(n)
时间复杂度O(n)空间复杂度O(1) 整个流程分三步
判断该链表是否有环如果有环确定环的长度根据环长设置快慢指针的起始位置移动快慢指针找到入口节点。
/*** 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) {ListNode meetingNode meetingNode(head);// 该链表无环返回nullif (meetingNode null) return null;// 链表有环从相遇点开始计数直到再次到达相遇点ListNode fast meetingNode;int cycleLength 1;while (fast.next ! meetingNode){fast fast.next;cycleLength;}System.out.println(cycleLength);// 快指针返回head并前进环长步数fast head;for (int i 0; i cycleLength; i){fast fast.next;}// 快慢指针开始移动每次移动一步相遇节点即为入口节点ListNode slow head;while (fast ! slow){fast fast.next;slow slow.next;}return fast;}public ListNode meetingNode(ListNode head){// 判断头节点是否为空if (head null) return null;// 定义快慢指针ListNode slow head.next;if (slow null) return null;ListNode fast slow.next;while (fast ! null slow ! null){if (fast slow) return fast;// 慢指针每次走一步快指针每次走两步slow slow.next;fast fast.next;if (fast ! null) fast fast.next;}return null;}
}2.2 快慢指针简化版 – O(n)
时间复杂度O(n)空间复杂度O(1) 思路基本和2.1一致不同的是这里简化了求环长直接让fast回到了头节点
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head, slow head;while (true) {if (fast null || fast.next null) return null;fast fast.next.next;slow slow.next;if (fast slow) break;}fast head;while (slow ! fast) {slow slow.next;fast fast.next;}return fast;}
} 3. 参考资料
[1] 剑指 Offer II 022. 链表中环的入口节点双指针清晰图解-- 2.2 题解参考
