搬瓦工 建网站,深圳乐创网站建设,企业网站功能是什么,wordpress租车每日OJ题—— 142. 环形链表 II #xff08;链表#xff09; 1.题目#xff1a;142. 环形链表 II 2.方法讲解2.1.解法一#xff1a;2.1.1.图文解析2.1.2.代码实现2.1.3.提交通过展示 2.2解法二:2.2.1图文解析2.2.2代码实现2.2.3.提交通过展示 1.题目#xff1a;142. 环形链… 每日OJ题—— 142. 环形链表 II 链表 1.题目142. 环形链表 II 2.方法讲解2.1.解法一2.1.1.图文解析2.1.2.代码实现2.1.3.提交通过展示 2.2解法二:2.2.1图文解析2.2.2代码实现2.2.3.提交通过展示 1.题目142. 环形链表 II 2.方法讲解
2.1.解法一
2.1.1.图文解析 我们使用两个指针fast 与 slow。它们起始都位于链表的头部。随后slow 指针每次向后移动一个位置而 fast 指针向后移动两个位置。如果链表中存在环则 fast 指针最终将再次与 slow 指针在环中相遇。 如下图所示设链表中环外部分的长度为 a。slow 指针进入环后又走了 b 的距离与 fast 相遇。此时fast 指针已经走完了环的 n 圈因此它走过的总距离为 an(bc)ba(n1)bncan(bc)ba(n1)bncan(bc)ba(n1)bnc。 根据题意任意时刻fast 指针走过的距离都为 slow 指针的 2 倍。因此我们有 a(n1)bnc2(ab) ⟹ ac(n−1)(bc)a(n1)bnc2(ab) ac(n-1)(bc) a(n1)bnc2(ab)⟹ac(n−1)(bc) 有了 ac(n−1)(bc)ac(n-1)(bc)ac(n−1)(bc) 的等量关系我们会发现从相遇点到入环点的距离加上 n−1n-1n−1 圈的环长恰好等于从链表头部到入环点的距离。 因此当发现slow 与 fast相遇时我们再额外使用一个指针 mind。起始它指向链表头部随后它和 slow 每次向后移动一个位置。最终它们会在入环点相遇。 2.1.2.代码实现 2.1.3.提交通过展示 2.2解法二:
2.2.1图文解析 这类链表题目一般都是使用双指针法解决的例如寻找距离尾部第 K 个节点、寻找环入口、寻找公共尾部入口等。 在本题的求解过程中双指针会产生两次“相遇”。 2.2.2代码实现 2.2.3.提交通过展示
