网站建设尾款放在什么科目里,国内做视频课程的网站有哪些,网站查询系统,网站 集约化建设 汇报❓142. 环形链表 II
难度#xff1a;中等
给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定…❓142. 环形链表 II
难度中等
给定一个链表的头节点 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 , 1 0 4 ] [0, 10^4] [0,104] 内 − 1 0 5 N o d e . v a l 1 0 5 -10^5 Node.val 10^5 −105Node.val105pos 的值为 -1 或者链表中的一个有效索引
进阶你是否可以使用 O ( 1 ) O(1) O(1) 空间解决此题
思路快慢指针
我们使用两个指针slow 与 fast它们起始分别指向链表的头部head 和头部的下一个节点head.next
随后slow 指针每次向后移动一个位置而 fast 指针向后移动两个位置。如果链表中存在环则 fast 指针最终将再次与 slow 指针在环中相遇。
如下图所示设链表中环外部分的长度为 a。slow 指针进入环后又走了 b 的距离与 fast 相遇。此时fast 指针已经走完了环的 n 圈因此它走过的总距离为: a n ( b c ) b an(bc)b an(bc)b 根据题意任意时刻fast指针走过的距离都为 slow 指针的 2 倍。因此我们有 a ( n 1 ) b n c 2 ( a b ) a(n1)bnc2(ab) a(n1)bnc2(ab) 整理得 a c ( n − 1 ) ( b c ) ac(n−1)(bc) ac(n−1)(bc) 我们会发现从相遇点到入环点的距离加上 n−1 圈的环长恰好等于从链表头部到入环点的距离。
因此当发现 slow 与 fast 相遇后我们让 fast 指向链表头部 headslow 指向slow 的下一个
随后 fast 和 slow 每次向后移动一个位置最终它们会在 入环点 相遇。
代码(Java、C)
Java
/*** 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(head null) return null;ListNode slow head;ListNode fast head.next;while(fast ! null fast.next ! null){if(slow fast) break;slow slow.next;fast fast.next.next;}if(fast null || fast.next null) return null;fast head;slow slow.next;while(slow ! fast){slow slow.next;fast fast.next;}return slow;}
}C
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head NULL) return NULL;ListNode* slow head;ListNode* fast head-next;while(fast ! NULL fast-next ! NULL){if(slow fast) break;slow slow-next;fast fast-next-next;}if(fast NULL || fast-next NULL) return NULL;fast head;slow slow-next;while(slow ! fast){slow slow-next;fast fast-next;}return slow;}
};运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)其中 n 为链表中节点的数目。在最初判断快慢指针是否相遇时slow 指针走过的距离不会超过链表的总长度随后寻找入环点时走过的距离也不会超过链表的总长度。因此总的执行时间为 O ( N ) O ( N ) O ( N ) O(N)O(N)O(N) O(N)O(N)O(N)。空间复杂度 O ( 1 ) O(1) O(1)我们只使用了 slow, fast 两个指针。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
