【C语言手撕算法】LeetCode-142. 环形链表 II（C语言）

前言： 本专栏将给大家带来一些有意思的算法题 希望对大家有所帮助 若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持!!! 谢谢大家 ! ! !

一、题目介绍

本篇是小编从leetcode上挑选的一道例题 同时，还是一道难度较大的面试题 就让我们来手撕这道面试题吧

下面是题目链接：

LeetCode-142. 环形链表 II

在这里插入图片描述

二、题目详解

1.审题

老规矩，拿到题目先审题，题目要求返回链表开始入环的第一个节点 所以，首先我们要判断该链表是否为环形链表，如果不是，那直接返回NULL就行了 若是环形链表该想办法找出返回链表开始入环的第一个节点

下面我一步一步带大家解出此题

2.判断是否为环形链表

（1）思路

如果链表不为环形链表，遍历链表就一定会走到空指针 但是如果是环形链表，遍历将会陷入死循环 总不能等到遍历死循环后再来判断是环形链表吧

这时候我想到了龟兔赛跑的故事 我们可以用一个快指针，一个慢指针来遍历链表 一个每次走2步，一个每次走1步，这样快指针每次就一定会比慢指针快一步

如果是环形链表：那个快指针就一定会先入环，当慢指针也入环后，快指针就会在环中一步一步追上慢指针 如果链表不为环形链表：快指针也无法再次与慢指针相遇，之后就一定会走到空指针

（2）代码演示

这里先创建快慢指针 然后用一个while循环，当fast走到NULL时结束 且当fast==slow时说明已经相遇，是环形链表，接着就只要找入环节点就行了

代码演示：

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *fast=head;//快指针
    struct ListNode *slow=head;//慢指针
    while(fast&&fast->next)
    {
        fast=fast->next->next;//每次走2步
        slow=slow->next;//每次走一步
        if(fast==slow)//相等就代表相遇
        {
            //F函数为找到入环节点函数（后面会讲）
            return F(head,fast);
        }
    }
    //当指针走到空指针就说明不是环形链表，返回NULL
    return NULL;
}

3.找到入环节点

（1）思路

现在已知是环形链表，那该怎么找到入环节点呢？

这里为了方便理解，画了一张草图 大家在做算法题的时候也应该多多画图，能更好的理解题目意思

首先设环的长度为C 设非环的长度为L 设相遇点与入环节点的距离为N

在这里插入图片描述

我们还可以写出fast和slow走的总距离: L ( fast ) = L + N + x * C (x为fast走的圈数) 由于fast比slow快，所以slow不可能走完一整圈环，走到一半就会被追上，所以有： L ( slow ) = L + N

又因为fast的速度是slow的两倍，于是就有 L ( fast ) = 2*L ( slow ) 带入得： L + N + x * C = 2 * ( L + N ) 化简得： x * C = N + L 变式得：( x - 1 ) * C + C - N = L 其中，左式相当于一指针走了（x-1）圈再加上C-N（图上标出了） 而右式就是头节点到入环节点的距离

所以 ! ! ! 我们让一个指针meet从fast与slow的相遇点开始走，让一个指针cur从头节点开始走 当meet在环内走了（x-1）圈时，再走C-N距离就会与走了L距离的cur相遇

（2）代码演示

这里先创建meet和cur,分别从相遇点和头节点开始以相同速度走 此时meet和cur的相遇点就是入环节点

struct ListNode *F(struct ListNode *head,struct ListNode *meet)
{
    struct ListNode *cur=head;
    while(1)//一定会找到，故用死循环，找到时就跳出循环
    {
        if(meet==cur)
        {
            //此时找到，任意返回一个值就行
            return meet;
        }
        meet=meet->next;
        cur=cur->next;
    }
}

三、考考大家

OK，本文【C语言手撕算法】LeetCode-142. 环形链表 II（C语言）到这里就结束了

但小编在这里给大家留下一个思考问题： 当慢指针的速度为 1 ，而快指针的速度为 3，4， 5…n 时，两指针还会相遇吗？ 有没有可能两人错过呢？大家可以去思考思考。

结语

本期资料来自于： https://leetcode.cn/

OK，本期的【C语言手撕算法】到这里就结束了

若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持

本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！

新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！

支持一下（三连必回QwQ）