您现在的位置是:首页 >学无止境 >图解LeetCode——142. 环形链表 II网站首页学无止境

图解LeetCode——142. 环形链表 II

爪哇缪斯 2024-06-17 11:19:03
简介图解LeetCode——142. 环形链表 II

一、题目

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。不允许修改 链表

二、示例

2.1> 示例 1:

输入】head = [3,2,0,-4], pos = 1
输出】返回索引为 1 的链表节点
解释】链表中有一个环,其尾部连接到第二个节点。

2.2> 示例 2:

输入】head = [1,2], pos = 0
输出】返回索引为 0 的链表节点
解释】链表中有一个环,其尾部连接到第一个节点。

2.3> 示例 3:

输入】head = [1], pos = -1
输出】返回 null
解释】链表中没有环。

提示:

  • 链表中节点的数目范围在范围 [0, 10^4] 内
  • -10^5 <= Node.val <= 10^5
  • pos 的值为 -1 或者链表中的一个有效索引

进阶:

  • 你是否可以使用 O(1) 空间解决此题?

三、解题思路

根据题目描述,我们需要返回链表开始入环的第一个节点。那么我们会最先想到的解题方式就是,创建一个Set集合,然后遍历整个链表,当遍历到某个节点的时候,发现该节点已经存在于Set集合中,则表示找到了入环的第一个节点,返回该节点即可。

但是本题在进阶部分提出了一个问题:你是否可以使用 O(1) 空间解决此题?那么我们就不能通过创建Set集合去解决这个问题了。那么我们来分析一下这个链表,以下图为例,我们将其拆分为非环形状a环形形状b两个部分。那么采用快慢指针fast&slow)的方式去遍历链表,由于快指针的速度是慢指针的2倍,所以我们可以得出以下结论,即:

fast指针行走的距离 = slow指针行走的距离 * 2;(我们简写为:fast= 2*slow

那么fast指针肯定先进入到循环链表中,随后slow指针才会进入到循环链表中,那么无论在链表中哪个节点处fast和slow相遇,我们都可以得出一个结论,即:

fast指针在循环链表中行走的距离 = slow指针在循环链表中行走的距离 * n圈 * b;(例如:跑步比赛被套圈了,此处我们简写为 fast = slow * nb

如果以slowfast在环中相遇的那个节点node为基准,那么,fast指针行走的总长度其实包含两个部分:

第1部分】从链表head开始到node的距离为:slow的行走距离
第2部分】以node为起始节点,fast行走的距离为:N圈*b

因此,我们可以得出如下推论:

因为fast = 2slow,并且fast = slow + Nb;
所以slow = N*b;

那么入环的第一个节点会是在哪个位置呢?其实就是a + Nb,那么我们就可以通过slow指针与fast指针的两次相遇,来计算出这个节点的位置了:

步骤1】slow行走1步,fast行走2步,当fast与slow相遇的时候,就是slow的行走距离,也就是Nb
步骤2】此时将fast指针指向head头节点,然后fast变为每次只行走1步,那么当fast行走了a距离的时候,就满足了 a + Nb长度了,fast和slow必然会相遇,而且是在入环的第一个节点位置上

以上就是本题的解题思路了,在下图中,通过举例的方式,一步一步的演示其执行逻辑,如下是步骤1的执行图例,请见下图所示:

如下是步骤2的执行图例,请见下图所示:

四、代码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        boolean isfast = true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = isfast ? fast.next.next : fast.next;
            if (slow == fast) { 
                if (isfast) { // 第一次相遇
                    isfast = false;
                    // 如果此时slow指向head,直接返回fast节点即可
                    if (slow == head) return fast; 
                    else fast = head;
                } else return fast;
            }
        }
        return null;
    }
}
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ (^o^)/ ~ 「干货分享,每天更新」

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。