LeetCode 142. 环形链表 II

LeetCode 142. 环形链表 II

题目描述

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

为了表示给定链表中的环,我们使用整数 p o s pos pos 来表示链表尾连接到链表中的位置(索引从 0 0 0 开始)。 如果 p o s pos pos 是 − 1 -1 −1,则在该链表中没有环。注意, p o s pos pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

示例 1:
LeetCode 142. 环形链表 II

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

示例 2:
LeetCode 142. 环形链表 II

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

示例 3:
LeetCode 142. 环形链表 II
输入: h e a d = [ 1 ] , p o s = − 1 head = [1], pos = -1 head=[1],pos=−1
输出:返回 n u l l null null
解释:链表中没有环。

提示:

链表中节点的数目范围在范围 [ 0 , 104 ] [0, 104] [0,104] 内
− 105 < = N o d e . v a l < = 105 -105 <= Node.val <= 105 −105<=Node.val<=105
p o s pos pos 的值为 − 1 -1 −1 或者链表中的一个有效索引

题目分析

关于环形链表

首先我们一般接触的链表是单链表有表尾,并且表尾结点的 n e x t next next 指针域是指向 N U L L NULL NULL 的。

那么如何判断一个链表是否有环呢?我们可以现从生活的一个例子来思考:

假设有 A A A 同学和 B B B 同学在操场上跑步,如果他们跑的都是直道,并且 B B B 同学的跑步速度大于 A A A 同学的跑步速度,那么在到达终点之前,他们两个都不可能相遇。
LeetCode 142. 环形链表 II
但是,如果是在环形跑道上跑步的话,那么 A A A 同学和 B B B 同学同时开始跑的时候,总有一个时刻, A A A 和 B B B 同学会相遇,并且 B B B 同学比 A A A 同学多跑了整数圈(具体整数多少取决于 B B B 同学的跑步速度)

LeetCode 142. 环形链表 II
对于链表来说,我们可以先设置两个指针指向头指针指向的结点,然后一个指针是快指针,一个指针是慢指针,它们分别代表 B B B 同学和 A A A 同学。然后我们设置快指针的速度是每次移动两个结点,而慢指针的速度是每次移动一个结点,也就代表了快指针的移动速度大于慢指针。

  1. 当链表没有环的时候,快指针一定会首先到达表尾或者是 N U L L NULL NULL 就好像上图直道跑步中, B B B 同学首先到达终点一样。
  2. 当链表有环的时候,那么根据上面的分析,快指针和慢指针一定会在某一个结点相遇,指向同一个结点,就像上图分析弯道跑步一样会在某一个时刻相遇。
    LeetCode 142. 环形链表 II
    LeetCode 142. 环形链表 II

关于入环口

假设有 A A A 同学和 B B B 同学从起点开始跑步,然后他们在首次相遇点相遇,如下图所示:

LeetCode 142. 环形链表 II

我们假设:

  1. 起点到入环口的距离为 D D D.
  2. 入环口到首次相遇点的距离为 S 1 S_1 S1​.
  3. 首次相遇点到入环口的距离为 S 2 S_2 S2​.

又因为当 A A A 同学和 B B B 同学第一次相遇的时候,他们所经过的时间是相同的,而且 B B B 同学多跑了 n n n 圈 ( n ≥ 1 ) (n\ge1) (n≥1)
又因为 V B = 2 V_B = 2 VB​=2 , V A = 1 V_A = 1 VA​=1,所以可以得出以下等式成立:
LeetCode 142. 环形链表 II
经过整理得:
LeetCode 142. 环形链表 II
以上表达式可以告诉我们:

  1. 如果 A A A 同学从起点开始走, B B B 同学从首次相遇点开始走,并且他们的速度都是匀速的。
  2. 当 B B B 同学走了 S 2 S_2 S2​距离到达入环口的时候, A A A 同学也走了 S 2 S_2 S2​ 距离,而且 A A A 同学还剩 ( D − S 2 ) (D-S_2) (D−S2​) 距离,根据以上等式也就是 ( n − 1 ) ( S 1 + S 2 ) (n-1)(S_1+S_2) (n−1)(S1​+S2​) 的距离。
  3. 所以当 A A A 同学继续往前走到达入环口的时候, B B B 同学一定从入环口走 ( n − 1 ) ( S 1 + S 2 ) (n-1)(S_1+S_2) (n−1)(S1​+S2​) 的距离再次到达入环口。因此这两个同学就在入环口相遇了。

算法分析

根据以上两个讨论,我们可以总结归纳出以下的算法:

  1. 首先用 f a s t fast fast 指针和 s l o w slow slow 指针都指向 h e a d head head 指向的第一个结点
  2. 每一次都判断 f a s t fast fast -> n e x t next next 和 f a s t fast fast 是否为 n u l l null null 值,如果判断是的话,则说明判断的链表是无环链表。
  3. 当 f a s t fast fast 指针和 s l o w slow slow 指针相等的时候,则说明他们两个指针指向同一个结点,则说明有环、
  4. 将 f a s t fast fast 指针指向首结点,把步长速度从 2 2 2 调整为 1 1 1 并且让 f a s t fast fast 指针和 s l o w slow slow 指针同时往后移动
  5. 等到他们再次相遇的时候,他们所指向的结点一定是入环口

代码如下:

/**
 1. Definition for singly-linked list.
 2. struct ListNode {
 3.     int val;
 4.     struct ListNode *next;
 5. };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;//让fast和slow都指向首结点
    while(1)//循环操作
    {
        if(fast == NULL || fast->next == NULL)
            return NULL;//当fast或者是fast->next指向空时,说明不是环形链表
            fast = fast->next->next;//fast的步长为2
            slow = slow->next;//slow的步长为1
        if(fast == slow)
            break;//当fast和slow相遇的时候,则不用继续往下走了,跳出while循环
    }
    fast = head;//把fast回到起点,slow在首次相遇点
    while(fast!=slow)//当fast和slow没有相遇的时候,以相同速度往前走
    {
        fast = fast->next;
        slow = slow->next;//步长都为1
    }
    return fast;//return slow也可以,因为他们相遇了
}

总结

  1. 如何判断有环和无环要清晰
  2. 算法问题要学会抽象化为数学问题求解
上一篇:leetcode 142. 环形链表 II 2


下一篇:FLINK基础(142):DS流与表转换(8) Handling of Changelog Streams(3) toChangelogStream