文章目录

  • 引言
  • 带环单链表之前 : 快慢指针
    • 题1:单链表的中间结点
    • 题2:链表中倒数最后k个结点
  • 带环链表分析
    • 题:环形链表
      • 带环链表的问题
      • ⭐带环链表深入分析⭐ *
        • 问题1
        • 问题2
        • 问题3
        • 题:寻找入环节点
  • 结语

引言

上一篇 【神秘海域】数据结构与算法 内容是 单链表及其接口

而本篇内容是对单链表的一个 非常重要 的补充: 带环单链表 。它,是大厂面试时可能会提问的内容,非常的重要!

本篇就是要结合题目来 详细分析一下 单链表的带环问题

带环单链表之前 : 快慢指针

在详细分析 带环单链表 之前,先分析两道题来了解一个非常重要的算法思路:快慢指针

题1:单链表的中间结点

原题描述是这样的:

给定一个头结点为 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

示例 1

输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 (测评系统对该结点序列化表述是 [3,4,5])
注意,我们返回了一个 ListNode 类型的对象 ans ,这样:
ans.val = 3 , ans.next.val = 4 , ans.next.next.val = 5 , 以及 ans.next.next.next = NULL .

示例 2

输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表 有两个中间结点 ,值分别为 34,我们 返回第二个结点

原题链接: Leetcode – 876. 链表的中间结点

这一题的解法,就需要使用到 快慢指针 的思路

那么什么是 快慢指针 ?即,使用两个 移动速度不同 的指针在 数组链表 等 序列结构上移动。

本题思路:

求链表的中间节点,就可以定义两个指针 : pslow 慢指针pfast 快指针

在本题中,快指针每次 移动两个节点 ,慢指针每次 移动一个节点 ,当快指针 走过尾节点为空(链表节点为单数) 或 指向尾节点(链表节点为双数) 时,慢指针应该 正好在中间节点

此时 慢指针所指节点 即为题目所求

代码实现:

struct ListNode* middleNode(struct ListNode* head){    struct ListNode* pfast = head;    struct ListNode* pslow = head;    while(pfast && pfast->next)    {        pfast = pfast->next->next;        pslow = pslow->next;    }    return pslow;}

题2:链表中倒数最后k个结点

此题描述是这样的:

例如,输入 {1,2,3,4,5}, 2 时,对应的链表结构如下图所示:

其中蓝色部分为该链表的最后2个结点,所以 返回倒数第2个结点(也即结点值为4的结点) 即可,系统会打印后面所有的节点来比较。

示例 1

输入:{1,2,3,4,5},2

返回值:{4,5}

说明:返回倒数第2个节点4,系统会打印后面所有的节点来比较。

示例 2:

输入:{2},8

返回值:{}

原题链接:Nowcoder – JZ22 链表中倒数最后k个结点

本题的思路也是使用快慢指针,但是与上一题不同的是,本题是先走为快指针 与 后走为慢指针

本题思路:

定义两个指针 : pslow 慢指针pfast 快指针,两指针均 一步一步走

快指针 先走 k 步,但同时要保证 快指针没走到空 ,如果 k 步没走完就已经走到空了,就表示链表没那么长

然后 慢指针 与 快指针 同时开始走,直到快指针走到空

此时 慢指针所指节点 即为题目所求

代码实现:

struct ListNode* FindKthToTail(struct ListNode* pHead, int k ){    struct ListNode* pfast = pHead;    struct ListNode* pslow = pHead;        while(k--)    {        if(pfast)        {            pfast = pfast->next;        }        else        {// 快指针指向空,即链表长度不到 k,直接返回 NULL            return NULL;        }    }    while(pfast)    {        pfast = pfast->next;        pslow = pslow->next;    }    return pslow;}


在分析带环链表之前,需要 需要了解一下 快慢指针 ,因为 带环链表的分析 是根据 快慢指针 分析的.

带环链表分析

分析 带环链表 ,先 由一道题来引入:

题:环形链表

此题描述:

给你一个链表的头节点 head ,判断链表中是否有环。

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

如果链表中存在环 ,则返回 true 。 否则,返回 false

示例 1

输入:head = [3,2,0,-4], pos = 1
返回:true
解释:链表中有一个环,其尾部连接到第二个节点

示例 2

输入:head = [1,2], pos = 0
返回:true
解释:链表中有一个环,其尾部连接到第一个节点

示例 3

输入:head = [1], pos = -1
返回:false
解释:链表中没有环

原题链接:Leetcode – 141. 环形链表

本题的思路也非常简单:

如果链表带环,那么使用 快慢指针pfast一次走两步,pslow一次走一步

两个指针就一定能相遇,因为 两指针均入环之后,两指针的距离是在一步步靠近的

不能相遇,就代表 链表不带环

代码实现:

bool hasCycle(struct ListNode *head){    if(head == NULL)        return false;    struct ListNode* pfast = head;    struct ListNode* pslow = head;    while(pfast && pfast->next)    {        pfast = pfast->next->next;        pslow = pslow->next;        if(pfast == pslow)            return true;    }    return false;}

OK,带环链表的题做出来了

但是并没有结束 如果只是这样 怎么会有大厂提问呢?


带环链表的问题

链表带环 的基础上,还会延伸出几个问题:

  1. 快指针一次走两步,慢指针一次走一步,两指针一定会相遇吗?为什么?
  2. 如果 快指针一次走两步呢?三步呢?四步呢?为什么?
  3. 怎么找到带环链表的 入环节点

这才是 带环链表 真正需要知道的东西~

⭐带环链表深入分析⭐ *

问题1

快指针一次走两步,慢指针一次走一步,两指针一定会相遇吗?为什么?

来详细分析一下:

画图抽象图来分析,一个带环链表,抽象的形式可以看作:

快慢指针 同时 从首节点开始走,快指针走得快,慢指针走得慢

所以慢指针入环时,快指针早就已经入环了

此时的情况可能是(设一下,只是假设)

两个指针都入环之后,快指针开始在环内追逐慢指针:

因为 当这样的两个指针都入环之后,两个指针之间的距离变化就变为了 每走一步减一

所以,必定会相遇

问题2

如果 快指针一次走三步呢?四步呢?为什么?

快指针一次走多步,就需要看情况来分析了

快指针一次走三步:

上边我们分析了 快指针一次走两步 时的相遇情况:当两个指针都入环之后,其之间的距离是以 每次缩小 1 变化的

那么如果 快指针一次走三步,那么 两个指针都入环之后,其之间的距离就是 以 每次缩小 2 变化的

每次缩小 2,会造成什么情况呢?

设 慢指针入环时,快指针和慢指针之间的距离为 X,环的长度为 C,那么就会有两种情况:当 X 为奇数,当 X 为偶数

情况 1: X 为 偶数

X(两指针之间的距离) 为偶数,两指针距离又是 每次减2 的变化,所以一定能相遇

情况 2: X 为 奇数此情况,快指针 超过 慢指针,但是由于快指针的移动是不连续的,所以两指针并不会相遇

其之间的距离变成了 -1,但是现在并不能直接判断是否能相遇,因为不能保证后面的追击能不能相遇

又因为 我们设环的长度为 C,所以此时 两指针之间的距离也是 C-1

所以,就又分为了两种情况:当 C-1 为奇数,当 C-1 为偶数

C-1 为 偶数的时候,这时,下次追击就可以相遇

C-1 为 奇数的时候,这时,就永远不会相遇了

为什么永远不会相遇?

C-1 为奇数时,也就意味着本次追击的 X(两指针之间的距离) 为奇数

X 为奇数,就又会出现 两指针之间的距离等于 -1 的情况,距离就有变成了 C-1

所以,当 C-1 为奇数时,永远不会遇到

快指针一次走四步:

当快指针 一次走四步 的时候,按照 一次走三步 的思路进行分析

  1. X3 的倍数,可以相遇
  2. X 不为 3 的倍数,且 C-1C-2 也不为 3 的倍数,就永远无法相遇
  3. C-1C-2 ,需要更详细的分析

也就是说,快指针 一次走多步 能不能与慢指针相遇是 不确定的

实际的情况,与 环的长度入环前链表的长度 都有关系,需要 具体情况具体分析

问题3

怎么找到带环链表的 入环节点

能够找到入环节点的一个前提是:快指针已经与慢指针相遇

详细分析一下:

首先还是画图假设一下:

先思考一个问题:慢指针 从入环到被追上 ,走过的长度 是不是如假设的那样,会不会已经走了一圈后才被追上的

答案是:不会

即使环再小,只有一个节点,慢指针那么在入环的一刻,就已经与快指针相遇了

如果环再长,慢指针也不可能走过一圈,因为快指针的速度是慢指针的两倍,慢指针如果走 超过一圈 ,那么快指针只会走 超过两圈

所以,慢指针一定是 在一圈之内被追上的,所以假设 是成立的。

参考图来看,慢指针 从开始与快指针相遇,走过的距离就是 :L + X

那么 快指针 走过的距离就是 : 2 * (L + X)

快指针走过的距离还可以怎么表示呢?

快指针走过的距离 还可以这样表示:L + X + N * C (N表示走过的圈数)

因为 快指针先入环,所以在慢指针入环之前,快指针很可能在环内已经走过几圈了

  1. L 很大 C很小时,快指针可能已经走了 N 圈了
  2. L 很小 C 很大时,快指针可能没有走超过一圈

所以,快指针 从开始与慢指针相遇 走过的距离,就可以写成一个等式:

2 * (L + X) = L + X + N*C

化简一下就是: L + X = N * C

这个式子有什么用呢?

其实,这个等式说明:

如果,有两个指针同时以一次一步的速度,一个从 链表的首节点 开始,另一个从 快慢指针相遇点 开始,两个指针会在环的入口节点相遇。

为什么呢?

L + X = N * C 可以写为 –> L = N * C - X

一个指针从 链表首届点开始走,走过 L 长度 它的位置在入环节点

一个指针从 快慢指针相遇点 开始走, 走过 N * C 的长度,它的位置还在 快慢指针相遇点 ,但是如果走过 N * C - X 的长度,那么它的位置就也在 入环节点了,因为 入环节点到快慢指针相遇点的距离是 X

此时,入环节点就找到了。

题:寻找入环节点

分析完如何寻找入环节点,下面来尝试把这道题给做了:

题目描述:

给定一个链表的头节点 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
解释:链表中没有环

原题链接:Leetcode – 142. 环形链表 II

代码实现:

// 大体思路与判断有环差不多// 但是 有环时不能直接返回struct ListNode *detectCycle(struct ListNode *head){    if(head == NULL)        return NULL;    struct ListNode* pfast = head;    struct ListNode* pslow = head;    while(pfast && pfast->next)    {        pfast = pfast->next->next;        pslow = pslow->next;        if(pfast == pslow)// 有环        {            struct ListNode* phead = head;            while(phead != pslow)//使 两个指针 分别从 首节点和相遇点 一次一步 移动,直到相遇            {                phead = phead->next;                pslow = pslow->next;            }            return phead;        }    }    return NULL;}


结语

本篇是对 单链表带环问题 的一个深入探索,单链表带环问题是 单链表中一个非常重要的应用 和 对单链表非常重要的理解。同时,他已经进入了大厂面试可能会考的范畴,重要的是对 单链表带环问题的深入分析而不是简单的判断是否有环

本篇文章到此结束

感谢阅读~


求评论、点赞、收藏~


博主其他文章推荐:
【神秘海域】[动图] 掌握 单链表 只需要这篇文章~ 「超详细」
【程序员的自我修养】[动态图文] 理解编译到链接的过程 [编译与链接一]
【程序员的自我修养】[动态图文] 超详解函数栈帧

有兴趣的可以关注一下博主的专栏:
⭐专栏:神秘海域:数据结构与算法
⭐专栏:《程序员的自我修养》