链表之第三回

这篇具有很好参考价值的文章主要介绍了链表之第三回。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链表之第三回,链表之108回,链表,网络,数据结构

欢迎来到我的:世界

该文章收入栏目:链表

希望作者的文章对你有所帮助,有不足的地方还请指正,大家一起学习交流 !


前言


今天的天气很不错😸,大早上起床,晨跑3公里,好久没这么跑了,真的很不错,我喜欢汗淋淋的感觉😄;暑假的假期时间也快到了,珍惜珍惜拥有自己所能支配的时间,来写几题吧✍️;


第一题:判断是否为环形链表


地址:oj地址


链表之第三回,链表之108回,链表,网络,数据结构
解题思路:

思路: 设置快慢指针,快指针 fast 每次走两个结点,慢指针 slow 每次走一个结点;如果是环形的,fast指针一定会和slow指针相遇,而且fast ,fast->next 走不到空(根据这两点做判断条件);如果不是环形,fast和slow一定不会相遇;可以根据这样的思路来写代码:
注意:
这个思路要想清楚

第一步

链表之第三回,链表之108回,链表,网络,数据结构

第二步:

链表之第三回,链表之108回,链表,网络,数据结构

第三步:相遇

链表之第三回,链表之108回,链表,网络,数据结构

代码实现:

bool hasCycle(struct ListNode *head) {
    struct ListNode *slow,*fast;
    //设置快慢指针
    slow=fast=head;
	//开始走,判断
    while(fast && fast->next)
    {
        fast=fast->next->next; //快指针一次走两步
        slow=slow->next;	   //慢指针一次走一步	
        if(fast==slow)//相遇则代表是环形
        {
            return true;
        }
    }
	//对于环形单链表,不可能有指向空指针
    return false;
}

第二题:找到两条链表的相交点


地址:oj地址


链表之第三回,链表之108回,链表,网络,数据结构

解题思路:

思路: 首先要判断,既然他如果是相交的,那最起码是有最后一个节点是相交的吧,那就判断两条链表最后一个结点是不是一样的;要知道应该是从相交点开始后面的所有结点应该都相等,所以重点就在相交结点前;

链表之第三回,链表之108回,链表,网络,数据结构

创造两个变量count1,count2,计算两条链表的结点总数;创造两个指针cur1,cur2指向两条链表的头结点headA,headB,由cur1和cur2去找最后一个结点(这里注意:判断的条件应该是cur1所指向的next !=NULL,因为这里我们要找到最后一个结点),计算两条链表的各结点的数量count1,count2,先让长的链表头结点先走 | count1 - count2 | (绝对值可以用 abs这个函数 )步,这个时候就可以两条链表的从头结点开始比较,如果相等则返回这个结点,如果不相等,就走向下一个结点直到找到相交结点(这里一定会找到相交结点,因为在上面的时候已经将不相交的情况排除了);

第一步:计算出两条链表的结点数量

链表之第三回,链表之108回,链表,网络,数据结构

第二步: 让长的链表头结点先开始走 | count1 - count2 | 步,注意这里用到绝对值;

链表之第三回,链表之108回,链表,网络,数据结构

第三步开始进行比较判断,如果相等则返回这个结点,如果不相等,就走向下一个结点直到找到相交结点

链表之第三回,链表之108回,链表,网络,数据结构

注意:这里让长的链表先走,一般想法是用if语句;这里我想换个更方便的方法:创造两个指针变量fast,slow;分别指向两条链表的头结点,这里只要一个判断:如果count1 小于 count2 让fast指向headB,而slow指向headA;思想就是始终让fast指向的是长链表,slow指向短一点的链表;在之后就可以直接使用fast,slow变量了;

代码实现:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int count1=1,count2=1;//计算两条链表的结点总数
    struct ListNode *cur1=headA;
    struct ListNode *cur2=headB;
	//找到headA链表的最后一个结点
    while(cur1->next)
    {
        cur1=cur1->next;
        ++count1;
    }
    //找到headB链表的最后一个结点
    while(cur2->next)
    {
        cur2=cur2->next;
        ++count2;
    }
	//结点不相等,则不可能相交;
    if(cur1!=cur2)
    {
        return NULL;
    }  
    //绝对值
    int len =abs(count1-count2);
    //始终让fast指向长链表,slow指向短一点的链表;
    struct ListNode*fast=headA,*slow=headB;
    if(count1<count2)
    {
        fast=headB;
        slow=headA;
    }
	//让其从相同位置结点开始比较;
    while(len--)
    {
        fast=fast->next;
    }
    //比较
    while(fast != slow)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return fast;

}

第三题:返回环形链表入环的那个结点


地址:oj地址


链表之第三回,链表之108回,链表,网络,数据结构
解题思路:

第一个简单的思路

设置两个指针fast和slow,fast一次走两步slow一次走一步,在环里的肯定会相遇,我们需要找到相遇的那个结点,然后断开这个结点与他后一个节点的链接,这样求入环点的问题就变成了:求两条链表的相交点;而求相交点的问题已经在上面解决了,是不是很简单理解;

链表之第三回,链表之108回,链表,网络,数据结构

将相遇点变成相交链表的尾巴,置成空;然后将相遇点tem下一结点设置成newnode指针,然后就是找相交点的问题了;

代码实现:

//实现找到相交结点并返回
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int count1=1,count2=1;//计算两条链表的结点总数
    struct ListNode *cur1=headA;
    struct ListNode *cur2=headB;
	//找到headA链表的最后一个结点
    while(cur1->next)
    {
        cur1=cur1->next;
        ++count1;
    }
    //找到headB链表的最后一个结点
    while(cur2->next)
    {
        cur2=cur2->next;
        ++count2;
    }
	//结点不相等,则不可能相交;
    if(cur1!=cur2)
    {
        return NULL;
    }  
    //绝对值
    int len =abs(count1-count2);
    //始终让fast指向长链表,slow指向短一点的链表;
    struct ListNode*fast=headA,*slow=headB;
    if(count1<count2)
    {
        fast=headB;
        slow=headA;
    }
	//让其从相同位置结点开始比较;
    while(len--)
    {
        fast=fast->next;
    }
    //比较
    while(fast != slow)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return fast;
}

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast=head,*slow=head;
    struct ListNode *tem=NULL,*newnode=NULL;
    
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        //找到相遇点
        if(slow==fast)
        {
            tem=slow;
            newnode=tem->next;
			//将相遇点变成链表的尾巴,置空;
            tem->next=NULL;

            //这边用我们之前写的求出相交结点
            return getIntersectionNode(head,newnode);
        }
    }
    return NULL;
}

这是一个思路比较容易理解的版本;还有一个比较难理解的思路:
是相似于物理的追击问题;
为来利用图解的方式;先进行这些假设:

链表之第三回,链表之108回,链表,网络,数据结构

这时候根据物理上的追击问题,根据fast和slow到相遇点所走的路程是一个两倍的关系;

链表之第三回,链表之108回,链表,网络,数据结构

所以:fast所走的距离是slow所走的距离的两倍;
slow走的距离是:L+X
fast走的距离是:L+X+n*C

  • 这里详解一下为什么fast走的距离是:L+X+n*C
    首先fast比slow走到快,当slow刚进入环,可能fast已经走了n圈环了(这个也是根据链表头结点到入环点的距离来判断的),且至少走了一圈了,当然不管他fast会绕多少圈,但他始终会在距离入环点 X的距离上的相遇点相遇的;

知道fast和slow所走的路程就可以用一个方程式:
2 * (L+X) = L+X+n * C (n>=1)化简得:
L = n * C - X
知道C - X 就是入口点;

链表之第三回,链表之108回,链表,网络,数据结构
无论fast走了多少圈C,C-X的距离就是相遇点到入环点的距离,无非是多绕了几圈,但是他们一定会在入环点相遇;

得出结论:一个指针从起点走,一个指针从相遇点走,他们一定会在入口点相遇;

代码的实现:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast=head,*slow=head;//快慢指针
    struct ListNode *tem=NULL;//相交点
    //成环进
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        //找到相遇点
        if(slow==fast)
        {
            tem=slow;
            //开始找交点
            while(head!=tem)
            {
                head=head->next;
                tem=tem->next;
            }
            return tem;
        }
    }
    //不成环就返回空
    return NULL;
}

总结


寻找环形链表的入环点的两种方法看似相同,其原理是不同的,看代码量也可以看出,前者是按照对环形的深刻理解方能很好的想到,而后者是根据其他知识求解出来的;如果还有更好的方法的老铁,可以在评论区里面一起进行讨论哦,在后面随着小孩的知识储备越多,小孩肯定还会加以优化优化!!


到了最后:感谢支持

我还想告诉你的是:
------------对过程全力以赴,对结果淡然处之
也是对我自己讲的
文章来源地址https://www.toymoban.com/news/detail-673291.html

到了这里,关于链表之第三回的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】- 链表之单链表(下)

    未来藏在迷雾中 叫人看来胆怯 带你踏足其中 就会云开雾散 本章是关于数据结构中的链表之单链表(下) 提示:以下是本篇文章正文内容,下面案例可供参考 1.2.1 在pos位置插入(也就是pos位置之前) 流程图 多个节点 一个节点 1.2.2 在pos位置之后插入 流程图: 注意: 下面这种写

    2023年04月23日
    浏览(60)
  • [数据结构]链表之单链表(详解)

    在学习 链表 之前,我们已经学习了 顺序表 了 根据 顺序表 的特点,我们可以发现 顺序表 有优点,也有一些缺陷。 所以根据 顺序表 的缺点,链表就横空出世啦~ **概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次

    2023年04月08日
    浏览(53)
  • 数据结构:线性表之-单向链表(无头)

    目录 什么是单向链表 顺序表和链表的区别和联系 顺序表: 链表: 链表表示(单项)和实现 1.1 链表的概念及结构 1.2单链表(无头)的实现 所用文件 将有以下功能: 链表定义 创建新链表元素 尾插 头插 尾删 头删 查找-给一个节点的指针 改 pos位置之前插入 删除pos位置的值 成品

    2024年02月09日
    浏览(63)
  • 数据结构:线性表之-循环双向链表(万字详解)

    目录 基本概念 1,什么是双向链表 2,与单向链表的区别 双向链表详解 功能展示: 1. 定义链表 2,创建双向链表 3,初始化链表 4,尾插 5,头插 6,尾删 判断链表是否被删空 尾删代码 7,头删 8,pos位置之前插入 优化后的头插 优化后的尾插 9,删除pos位置的节点 优化后的尾删 优

    2024年02月09日
    浏览(49)
  • 数据结构(王道)——线性表之静态链表&顺序表和链表的比较

      如何定义一个静态链表     初始化静态链表:   静态链表的查找、插入、删除           创: 销:   增、删:   查:   顺序表、链表该如何选择?  

    2024年02月16日
    浏览(104)
  • 第三百五十三回

    我们在上一章回中介绍了\\\"分享一些好的Flutter站点\\\"相关的内容,本章回中将介绍timezone包.闲话休提,让我们一起Talk Flutter吧。 我们在前面章回中介绍了获取当前时区的内容,本章回将介绍一个与时区相关的包,它虽然不能获取到当前时区,但是可以查看所有的时区,而且可以

    2024年02月20日
    浏览(49)
  • 线性表之链表

    在计算机科学中,链表是一种常见的数据结构,用于存储和组织数据。相比于顺序表,链表具有更高的灵活性和动态性。 在本博客中,我们将深入讨论链表的概念、分类以及实现方法。我们将从链表的基本概念开始,了解链表是如何组织数据的,并分析链表的优势和劣势。

    2024年02月11日
    浏览(33)
  • DS线性表之链表

    我们上一期介绍了顺序表,它的底层就是数组,我们也分别对顺序表的动态版本和静态版本进行了实现!并且分析了顺序表的优缺点,优点是:尾插、尾删效率很高,其时间复杂度是O(1);缺点是:在头部插入、删除的时候效率低,其时间复杂度是O(N);而且即使是动态版本的扩

    2024年02月08日
    浏览(38)
  • 线性表之双向链表(详解)

    🍕博客主页:️自信不孤单 🍬文章专栏:数据结构与算法 🍚代码仓库:破浪晓梦 🍭欢迎关注:欢迎大家点赞收藏+关注 在前面我们已经学习了链表中的单链表,今天我们再来学习另一个常用的链表结构: 带头双向循环链表 。 首先创建两个文件来实现双向链表: List.h(节

    2024年02月06日
    浏览(31)
  • 【日常Exception】第三十三回:Flink运行jar包报错NoSuchMethodError: org.apache.flink.api.common.functions.Runtime....

    主要报错内容: java.lang.NoSuchMethodError: org.apache.flink.api.common.functions.RuntimeContext.getMetricGroup()Lorg/apache/flink/metrics/MetricGroup; 报错全量信息: 原因: 升级后使用的flink安装版本是1.14.5,而我的jar包中是使用的1.13.2 解决: 将jar包中的pom中flink的依赖版本,也换成1.14.5,与服务器上

    2024年02月16日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包