草庐IT

链表OJ之 快慢指针法总结

Claffic 2023-04-15 原文

欢迎来到 Claffic 的博客 💞💞💞 

前言：

快慢指针指的是每次指针移动的步长，是解决链表相关的题目的一大利器，下面我将以例题的形式讲解快慢指针法。 

目录

一. 链表的中间结点

思路：

代码实现：

二. 链表中倒数第k个结点

思路：

代码实现：

三.  判断链表中是否有环

思路：

代码实现：

四. 返回链表入环的第一个结点

思路：

代码实现：

一. 链表的中间结点

点我做题

思路：

创建两个快慢指针 slow , fast ，起始共同指向头节点，slow 每次走一步，fast 每次走两步，当 fast 为空或 fast 的下一个结点为空时，slow  即是中间节点的位置。

解释：

由于 fast 每次走两步，slow 每次走一步，slow 总是落后 fast 整体一半的长度最终 slow 理应为中间结点。

结点数为奇数：

最终 fast 在最后一个结点，此时结束的标志为 fast->next == NULL；

结点数为偶数：

最终 fast 在最后一个结点的下一个指向，此时的结束标志为 fast == NULL; 

代码实现：

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow,*fast;
    slow = head;
    fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

二. 链表中倒数第k个结点

点我做题

思路：

同样，创建两个快慢指针 slow , fast ，起始共同指向头节点，先让 fast 走 k 步，再让 fast 和 slow 同时前进，直到 fast 为空为止。

解释： 

先让 fast 走 k 步，那么 fast 与 slow 之间就隔了 k-1 个结点，fast 与 slow 同时前进，直到 fast 为空时，fast 与 slow 之间依然隔 k-1 个结点，那就是倒数第 k 个结点。

代码实现：

int kthToLast(struct ListNode* head, int k){
    struct ListNode* fast,*slow;
    fast = slow = head;
    if(head == NULL)
    {
        return NULL;
    }
    //fast 前进 k 步
    while(k--)
    {
        fast = fast->next;
    }
    //slow 与 fast 共同前进
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    //注意返回的是整型数值
    return slow->val;
}

三.  判断链表中是否有环

点我做题

思路：

快慢指针 slow , fast，都从 head 开始，slow 一次走一步，fast 一次走两步，如果 slow 和 fast 能相遇，则链表有环。

解释：

主要是证明 有环情况下两个指针一定能相遇：

fast 比 slow 先进入环，如图，假设 slow 和 fast 的位置，这两个指针之间差 N 步，

由于 fast 每次走两步，slow 每次走一步，所以 slow 和 fast 之间的距离每次缩短 1 

N - 1

N - 2

N - 3

...

2

1

0    //此时两者相遇

证毕。 

代码实现：

bool hasCycle(struct ListNode* head) {
    struct ListNode* fast,*slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}

四. 返回链表入环的第一个结点

点我做题

思路：

这里要先放一个结论：

在链表有环的情况下，一个指针在起始结点开始走，另一个结点在相遇点开始走，最终两个指针会在入环点相遇。

快慢指针 slow , fast，都从 head 开始，slow 一次走一步，fast 一次走两步，找到相遇点后，再让 start 与 meet 同时前进，两者相等的点即是入环点。

解释：

自然要证明上边的结论：

在这里，我们设几个常量：

L：起始点到入环点的距离；

X：入环点到相遇点的距离；

C：环的周长。

已知条件：

slow 走的距离：L + X ；

fast 走的距离：L + n*C + X (n >=1) ；

fast 走的长度是 slow 走的长度的 2 倍。

推导：

fast 走的长度是 slow 走的长度的 2 倍 --> 

2*(L + X)  == L + n*C + X (n >=1)，

整理得：L == C - X + (n - 1)*C  (n >=1).

对 L == C - X + (n - 1)*C  (n >=1) 的解释：

C - X + (n - 1)*C  (n >=1) 原本是 meet 到 innode 要走的所有可能距离，

而 L == C - X + (n - 1)*C  (n >=1) ，说明 start 到 innode 要走的距离与 meet 到 innode 要走的所有可能距离相等，所以两者相遇的点一定是 innode.

代码实现：

struct ListNode* detectCycle(struct ListNode *head) {
    struct ListNode* slow,*fast;
    slow = fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast)
        {
            struct ListNode* meet = slow;
            struct ListNode* start = head;

            while(meet != start)
            {
                meet = meet->next;
                start = start->next;
            }
            return meet;
        }
    }
    return NULL;
}

总结：

快慢指针是解决链表问题的一大利器，建议多画图理解掌握。 

码文不易 

如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦  💗💗💗

针法快慢strongxfffast链表数据结构c++c语言

有关链表OJ之 快慢指针法总结的更多相关文章

  1. SPI接收数据异常问题总结 - 2

    SPI接收数据左移一位问题目录SPI接收数据左移一位问题一、问题描述二、问题分析三、探究原理四、经验总结最近在工作在学习调试SPI的过程中遇到一个问题——接收数据整体向左移了一位（1bit）。SPI数据收发是数据交换，因此接收数据时从第二个字节开始才是有效数据，也就是数据整体向右移一个字节（1byte）。请教前辈之后也没有得到解决，通过在网上查阅前人经验终于解决问题，所以写一个避坑经验总结。实际背景：MCU与一款芯片使用spi通信，MCU作为主机，芯片作为从机。这款芯片采用的是它规定的六线SPI，多了两根线：RDY和INT，这样从机就可以主动请求主机给主机发送数据了。一、问题描述根据从机芯片手

  2. Simulink方法总结和避坑指南（一）——Simulink入门与基本调试方法 - 2

    文章目录一、项目场景二、基本模块原理与调试方法分析——信源部分：三、信号处理部分和显示部分：四、基本的通信链路搭建：四、特殊模块：interpretedMATLABfunction：五、总结和坑点提醒一、项目场景  最近一个任务是使用simulink搭建一个MIMO串扰消除的链路，并用实际收到的数据进行测试，在搭建的过程中也遇到了不少的问题（当然这比vivado里面的debug好不知道多少倍）。准备趁着这个机会，先以一个很基本的通信链路对simulink基础和相关的debug方法进行总结。  在本篇中，主要记录simulink的基本原理和基本的SISO通信传输链路（QPSK方式），计划在下篇记

  3. 【动态规划】背包问题（详细总结，很全） - 2

    【动态规划】一、背包问题1.背包问题总结1）动规四部曲：2）递推公式总结：3）遍历顺序总结：2.01背包1）二维dp数组代码实现2）一维dp数组代码实现3.完全背包代码实现4.多重背包代码实现一、背包问题1.背包问题总结暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！背包问题是动态规划（DynamicPlanning）里的非常重要的一部分,关于几种常见的背包，其关系如下：在解决背包问题的时候，我们通常都是按照如下五部来逐步分析，把这五部都搞透了，算是对动规来理解深入了。1）动规四部曲：（1）确定dp数组及其下标的含义（2）确定递推公式（3）dp数组的初始化（4）确定遍历顺

  4. 【数据结构和算法】实现带头双向循环链表（最复杂的链表） - 2

    前文，我们实现了认识了链表这一结构，并实现了无头单向非循环链表，接下来我们实现另一种常用的链表结构，带头双向循环链表。如有仍不了解单向链表的，请看这一篇文章(7条消息)【数据结构和算法】认识线性表中的链表，并实现单向链表_小王学代码的博客-CSDN博客目录前言一、带头双向循环链表是什么？二、实现带头双向循环链表1.结构体和要实现函数2.初始化和打印链表3.头插和尾插4.头删和尾删5.查找和返回结点个数6.在pos位置之前插入结点7.删除指定pos结点8.摧毁链表三、完整代码1.DSLinkList.h2.DSLinkList.c3.test.c总结前言带头双向循环链表，是链表中最为复杂的一种结

  5. ruby-on-rails - 错误 : Error installing oj: - 2

    我刚刚第一次从GitHub克隆了一个存储库。我去我的本地机器上检查了它，所以在我的mac上的本地存储库中我运行了以下命令bin/rails服务器我收到以下错误:无法在任何来源中找到activesupport-5.0.0.1运行bundleinstall以安装缺少的gem。然后我按照建议运行了bundleinstall命令，但是它给了我以下错误安装oj(2.12.14)时出错，Bundler无法继续。确保geminstalloj-v'2.12.14'在捆绑之前成功。所以我按照建议运行了:geminstalloj-v'2.12.14'然后我收到一条非常长的消息，其中包含警告和错误(见下文)

  6. 相机面试问题总结 - 2

    1，Camera基本工作原理答案：光线通过镜头Lens进入摄像头内部，然后经过IRFilter过滤红外光，最后到达sensor（传感器），senor分为按照材质可以分为CMOS和CCD两种，可以将光学信号转换为电信号，再通过内部的ADC电路转换为数字信号，然后传输给DSP（如果有的话，如果没有则以DVP的方式传送数据到基带芯片baseband，此时的数据格式RawData，后面有讲进行加工）加工处理，转换成RGB、YUV等格式输出。数据流是如何从sensor到APP的？上述描述结束后，在ISP处理后面的阶段，数据会进行分流，分为capture,preview，video等以供后续动作使用。例如

  7. 【结构与算法】—— 数据结构代码总结 | 数据结构代码大全 - 2

    📢博客主页：https://blog.csdn.net/dxt19980308📢欢迎点赞👍收藏⭐留言📝如有错误敬请指正！📢本文由肩匣与橘编写，首发于CSDN🙉📢生活依旧是美好而又温柔的，你也是✨目录🔴线性表1.1顺序表1.1.1顺序表定义1.1.2顺序表基本操作1.2单链表1.2.1单链表节点定义1.2.2单链表基本操作1.3双链表1.3.1双链表节点定义1.3.2双链表基本操作1.4静态链表🟠栈和队列2.1栈2.1.1顺序栈2.1.2链式栈2.2队列2.2.1顺序队列2.2.2链式队列2.3应用🟡串3.1串的定义与实现3.2串的模式匹配🟢树与二叉树4.1二叉树4.1.1二叉树的概念4.1.2

  8. MyBatisPlus总结 - 2

    目录MyBatisPlusMP特点MP框架结构MP使用准备导入依赖springboot整合mybatisplus配置文件定义好实体类User后编辑mapper接口@Mapper与@MapperScan("包名")区别MP基本操作新增操作删除操作通过id删除用户通过map作为条件删除通过多个id实现删除更新用户通过id进行用户更新查询用户 根据id查询用户根据多个id查询用户根据map集合作为条件查询用户通用Service接口一些操作 查询总记录数批量添加数据MP常用注解雪花算法前言垂直分表水平分表条件构造器继承结构使用条件构造器实现查询操作查询所有用户根据构造器查询主键字段集合根据条件构造器查

  9. Solidity合约内创建合约以及引用其他合约的总结 - 2

    本文总结了在以太坊智能合约中使用Solidity在合约内创建合约以及引用其他合约的方法，包括了如何使用mochai进行测试的方法。在这之前先明白一个比较：Contract{}相当于面向对象语言的类当部署后获得到address后，address相当于对象，address0x.......本身就类似指针地址然后我们讨论下Solidity代码中对合约类，合约对象的操作。Solidity首先区分下三种写法：import'ContractB.sol';ConractBB=newConractB(arg1,arg2...);ContractBB=ContractB(Baddress);functionse

  10. ruby - Ruby 有像栈、队列、链表、映射或集合这样的容器吗？ - 2

    我在网上查了几个Ruby教程，他们似乎什么都用数组。那么如何在Ruby中实现以下数据结构呢？堆栈队列链表map组 最佳答案 (从评论中移出)好吧，通过限制堆栈或队列方法(push、pop、shift、unshift)，数组可以是堆栈或队列。使用push/pop提供LIFO(后进先出)行为(堆栈)，而使用push/shift或unshift/pop提供FIFO行为(队列)。map是hashes,和一个Set类已经存在。您可以使用类实现链表，但数组将使用标准数组方法提供类似于链表的行为。 关

随机推荐