数据结构刷题训练——链表篇(三)

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

目录

文章目录

前言

1. 题目一:环形链表Ⅱ

1.1 思路

1.2 分析

1.3 题解

1.4 方法二

2. 题目二:复制带随机指针的链表

2.1 思路

2.2 分析

2.3 题解

总结


前言

        在这个专栏博客中,我们将提供丰富的题目资源和解题思路,帮助读者逐步提高解题能力。同时,我们也将分享一些刷题技巧和经验,帮助读者更加高效地进行刷题训练。通过持之以恒的努力和不断的实践,相信读者可以在数据结构领域取得长足的进步。本期将是数据结构刷题训练链表篇的最后一期,后续我们将进入栈和堆的刷题训练。


1. 题目一:环形链表Ⅱ

题目描述:

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

示例:

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

 题目链接:环形链表Ⅱ

1.1 思路

        本题的题意是给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 NULL。

        寻找第一个入环的节点,在上道环形链表的题目中仅仅只是判断是否有环,但没法确定入环的节点,这道题目属于之前题目的进阶。那我们要如何去解决呢?

        这里向大家说明一点,如果在刷题的时候,遇到一个题目,连题意都很难理解或者,是无从下手,那这道题目就不再是简简单单的考察代码能力,其中的分析更为重要,没有分析的过程,仅仅只要代码是无法看懂理解的。

1.2 分析

        初看题目毫无思路,但是别担心,我在分析之后记住这种做题思路、方法就可以,在后续刷题中灵活运用。这道题目我们仍然可以使用快慢指针的方法。

        首先我们需要知道带环链表的几种情况:

一般情况:

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

 环很大

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

 

 环很小

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

         在上期中我们将道使用快慢指针遍历链表,快指针一次走两步,慢指针一次走一步,如果它们相遇那它们一定是带环的链表。那问题来了,fast一次走两步,slow一次走一步,一定可以追上吗? 结论是一定能追上。

        为什么?我们可以分析一下,在两个指针都入环以后,快指针一次走两步,慢指针一次走一步,它们的距离会减一,一直走一直减一,最后直到追上,距离变化过程:

N

N-1

N-2

……

2

1

0

        那如果fast一次走3步,slow一次走两步呢?

        假设它们之间的距离是M,fast和slow都进环以后,它们的距离一次就是减2,那它们的距离变化:

M是偶数          M是奇数

M-2                  M-2

M-4                  M-4 

……                  ……

4                        3

2                        1

0                      -1

         如果M是偶数,就刚好追上相遇,如果M是奇数这就说明它们会错过,一旦错过就要继续走一圈,假设环的周长是C,当C为奇数时,当它们错过后,它们之间的距离是C-1,此时C-1必为偶数,下次一定能追上,但如果C是偶数时,C-1为奇数,然而它们每次距离减小2,这样无论怎么走都不会相遇。

         如果继续增大步数呢?fast一次走4步,slow一次走两步。假设进入环后它们的距离是k,那么它们的距离变化:

k是3的倍数          k%3=2            k%3=1

k-3                        k-3                  k-3

k-6                        k-6                   k-6

……                     ……                  ……

6                             5                     4

3                             2                     1

0                            -1                    -2

错过后距离:         C-1                 C-2

         如果C-1或C-2仍然不是3的倍数,那它们仍然始终无法相遇。有人可能会这样想,那让其中一个停下来,另一个去追不就可以了,但我们无法确定慢指针是否进环了,如果没进环,那快指针走多少圈都不会追上。这里只是移动步数的分析,在带环链表中使用快慢指针,最好使用步数差为1的,下面步入正题:

        依据上述结论,我们看这道题目,这里我们让fast一次走2步,slow一次走1步,当fast入环时:

        假设从起点到入环点距离为L,环周长为C

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

 慢指针入环时:数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

 

 相遇时:

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

         由上可以得出:fast走的距离时slow的二倍,那slow走的距离就是X+L,那fast走的路程就是L+X+n*C(n>=0),因为无法确定L于C的关系,如果C很小,那fast就可能走了很多圈。或许有人会疑惑,那slow为什么不用加n*C,因为slow入环以后,fast在slow走一圈之内一定能追上它

 我们根据这些关系可以得到:

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

化简一下:

L+X=n*C

n*C-X=L

 得到n*C-X=L这个结论再转化一下就是:(n-1)*C+C-X=L

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

         到这里就一目了然了,一个指针从相遇点开始出发,一个从起点开始出发,最终它们会在入环点相遇。

1.3 题解

根据上述的分析进行编写代码:

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;
            while(meet!=head)
            {
                head=head->next;
                meet=meet->next;
            }
            return head;
        }
    }
    return NULL;
}

1.4 方法二

        方法二的思路简单,但代码量增多,我们先让两指针相遇,相遇后将相遇的节点的next置为NULL,也就是将环断掉,这样就转化成了链表相交。

 代码如下:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* curA=headA,*curB=headB;
    int lenA=1,lenB=1;
    while(curA->next)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }
    if(curA!=curB)
    {
        return NULL;
    }
    int t= abs(lenA-lenB);
    struct ListNode* longlist=headA, *shortlist=headB;
    if(lenB>lenA)
    {
        longlist=headB;
        shortlist=headA;
    }
    while(t--)
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}
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* newnode=meet->next;
            meet->next=NULL;

            return getIntersectionNode(newnode,head);
           
        }
    }
    return NULL;
}

2. 题目二:复制带随机指针的链表

 题目描述:数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

 示例:

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

 题目链接:

复制带随机指针的链表

2.1 思路

        或许大部分人读完题目还是像上道题目一样,读完没有思路,甚至连题意都读不懂。

        复制一个链表不难,但这道题目的难点在于每个节点指针域的随机指针,我们很难控制随机指针的指向,单纯的完全复制行不通,复制下来的节点关系要与原链表相同,这才是本道题目的难点。

怎么才能找到随机指针的指向关系呢?

我们的思路是这样的:

  • 遍历原链表,遍历一个节点复制一个节点,然后将复制的节点插入道原节点的后边。
  • 再次遍历插入后的链表,找复制节点的随机指针的指向关系。
  • 最后将复制的链表与原链表分开

2.2 分析

 根据思路进行分析:

 复制后的链表链接道原链表

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

 这里要理解如何去找复制节点的random指向的节点。

我们可以这样操作:copy->random=cur->random->next

         重点就是这句的理解,cur指向的是原链表中的节点,复制的也就是cur指向的节点,然后将复制的节点(copy)链接到cur节点后,那copy节点的random不就在cur节点的random指向节点的下一个吗?

        意思就是说,遍历原链表中的节点,找到当前节点的random就可以找到复制节点的random,因为复制节点(copy)的random,就是当前节点(原链表)random指向节点的下一个节点。

数据结构刷题训练——链表篇(三),数据结构,链表,算法,leetcode,c语言

         这里要好好理解,例如:13号这个节点(cur),13节点的下一个节点就是复制的13号节点。cur的random指向的是7号节点(原链表),7号节点的下一个节点不就是复制的13号节点(copy)要找的random吗?

        但这里需要特殊处理一种情况,就是原链表random指向为NULL的情况,这里就直接将复制节点的random置为NULL。

2.3 题解

根据上述的分析,开始编写代码:

struct Node* copyRandomList(struct Node* head)
{
	struct Node* cur=head;
    while(cur)                    //复制节点
    {
        struct Node* copynode=(struct Node*)malloc(sizeof(struct Node));
        struct Node* next=cur->next;
        copynode->val=cur->val;
        
        //插入到原节点后
        cur->next=copynode;
        copynode->next=next;
        
        cur=next;
    }
    cur=head;
    
//寻找复制节点的random
    while(cur)        
    {
        struct Node* copynode=cur->next;
        if(cur->random==NULL)        //随机指针为NULL进行特殊处理
        {
            copynode->random=NULL;
        }
        else
        {
            copynode->random=cur->random->next;
        }
        
        cur=cur->next->next;
    }
     cur=head;
     struct Node* copyhead,*copytail;
     copyhead=copytail=NULL;

//还原原节点,将两个链表分开
    while(cur)
    {
        
        struct Node* copynode=cur->next;
        struct Node* next=cur->next->next;
        //将复制节点链接到新的链表,这里使用的是无头节点的链表,所有需要特殊处理
        if(copyhead==NULL)
        {
            copyhead=copytail=copynode;
        }
        else
        {
            copytail->next=copynode;
            copytail=copytail->next;
        }
        //恢复原链表
        cur->next=next;
        cur=next;

    }
    return copyhead;
}

 

总结

        本期的题目相对较为复杂,希望大家能够好好的消化理解,最后,感谢你的阅读和支持。希望你在这个数据结构的学习旅程中能够获得满满的收获和成就感。愿我们共同努力,不断探索和挑战,成为数据结构领域的行家里手!文章来源地址https://www.toymoban.com/news/detail-637284.html

到了这里,关于数据结构刷题训练——链表篇(三)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • LeetCode 刷题 数据结构 链表 203 移除链表元素

    Given the  head  of a linked list and an integer  val , remove all the nodes of the linked list that has  Node.val == val , and return  the new head . Example 1: Example 2: Example 3: Constraints: The number of nodes in the list is in the range  [0, 104] . 1 = Node.val = 50 0 = val = 50 今天leetcode的中文官网比较卡,所以是登录官网进行

    2024年02月14日
    浏览(33)
  • 算法刷题营【Day3】:: 链表篇:单链表结点删除思路:一题辨别哨兵结点的优势(删除有奇效):203. 移除链表元素

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:203. 移除链表元素 2. 题解参考 - - 2.1 方法一:原表操作(不含哨兵结点) - - 2.2 方法二:虚设哨兵结点辅助法 - - 2.3 方法三:递归法 3. 单链表结点删除思路 4. 方法思路点拨:原表操

    2024年02月06日
    浏览(47)
  • 数据结构刷题训练:队列实现栈

    目录 前言 1. 题目:使用队列实现栈 2. 思路 3. 分析  3.1 创建栈 3.2入栈 3.3 出栈 3.4 栈顶数据 3.5 判空和 “ 栈 ” 的销毁  4. 题解 总结         我们已经学习了栈和队列,也都实现了它们各自的底层接口,那么接下我们就要开始栈和队列的专项刷题训练。 题目描述:  题

    2024年02月13日
    浏览(34)
  • 数据结构刷题训练——二叉树篇(一)

    📙 作者简介:  清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。 📘 相关专栏: C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正! ✨每一次努力都

    2024年02月07日
    浏览(51)
  • 数据结构刷题训练:设计循环队列(力扣OJ)

    目录 文章目录 前言 1. 题目:设计循环队列 2. 思路 3. 分析  3.1 定义循环队列  3.2 创建队列  3.3 判空和判满  3.4 入队  3.5 出队  3.6 取队头队尾数据  3.7 销毁队列  4. 题解 总结         当谈到队列数据结构时,很多人可能会想到普通的队列,即先进先出(FIFO)的数据结

    2024年02月13日
    浏览(47)
  • 趣说数据结构(练习2) —— 顺序表/链表力扣刷题(中等难度)

    力扣原题:https://leetcode.cn/problems/reverse-linked-list-ii/ 题目描述 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left = right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 示例 1 输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5] 示例 2 输入:h

    2024年02月01日
    浏览(45)
  • 数据结构刷题训练:用栈实现队列(力扣OJ)

    目录 前言 1. 题目:用栈实现队列 2. 思路 3. 分析  3.1 定义 “ 队列 ”  3.2 创建队列 3.3 入队  3.4 队头数据  3.5 出队  3.6 判空和销毁 4.题解 总结         栈和队列是数据结构中的两个重要概念,它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用

    2024年02月13日
    浏览(37)
  • 数据结构之顺序表篇

    一、顺序表概念 二、顺序表各类接口实现 *顺序表初始化 **顺序表销毁 ***顺序表插入操作 ****顺序表删除操作 *****顺序表查找操作 ******顺序表实现打印操作 三、顺序表整体实现源码 *SeqList.h **SeqList.c ***test.c 讲顺序表之前先引入线性表概念,线性表是n个有相同特性的数据元素

    2024年02月02日
    浏览(32)
  • LeetCode刷题系列之----->(指针玩转链表篇)(三)

    🍉博客主页:阿博历练记 📖文章专栏:数据结构与算法 🔍代码仓库:阿博编程日记 🌹欢迎关注:欢迎友友们点赞收藏+关注哦 现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后

    2024年02月04日
    浏览(38)
  • 【数据结构与算法】链表

    对于顺序表存在一些缺陷: 中间/头部的插入删除,时间复杂度为O(N) 。头部插入需要挪动后面的元素 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插

    2023年04月09日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包