【数据结构】链表相关题目(中档题)

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

【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode

🚀write in front🚀
📜所属专栏:初阶数据结构
🛰️博客主页:睿睿的博客主页
🛰️代码仓库:🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!!
关注我,关注我,关注我你们将会看到更多的优质内容!!

【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode

前言:

  在前面的练习中,我们简单练习了链表的相关题目,今天我们在来做一些拓展!

例题1:

在这里插入图片描述【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode

方法1:

  在上一篇博客里面,我们讲述了快慢指针的概念:通过步长的差异处理环的问题。而这道题我们要寻找入口点,我们该如何处理呢?

首先,我们假设

  • 起始点到入口的长度为L,
  • 入口到相遇点的距离为X,
  • 环的长度为C。

接下来我们通过快慢指针的两个性质(快指针是慢指针步数的两倍,快慢指针最后相遇)列出一个方程:
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode
  由得出的结论我们可以看出,如果让一个指针a从起点出发,另一个指针b从相遇点出发,如果是闭环,则他们一定会相遇!(这里我们并不需要算出n的值,因为n的值是是让a指针多走n-1个整圈,不影响和b指针相遇)。
下面我们来看看代码:

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode*slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
            struct ListNode*cur=head;
            while(cur!=slow)
            {
                cur=cur->next;
                slow=slow->next;
            }
            return slow;
        }
    }    
    return NULL;
}

方法2:

  如果同学们在做题时无法自己推出这个结论,那么此时我们也可以将相遇点断开,此时就变成了寻找公共节点的题目了。
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode

例题2:

【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode
对于这道题目,大家可能最先会想到计数器的方法,通过记录每个random的位置,在拷贝的链表里面找到对于位置依次连接。但是这样会导致时间复杂度非常的低下:O(N^2)
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode
为了降低复杂度,就不得不使用另外一种方法。要降低时间复杂度,我们就希望能快速的找到原节点的拷贝节点。怎么找呢?

1.拷贝节点链接在原节点后面
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode

2.此时拷贝节点的random就是原节点random->next
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode

3.拷贝节点解下来,链接成新链表,最后将原链表还原。
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode
【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode

完整代码:

struct Node* copyRandomList(struct Node* head) 
{
	//第一步
    struct Node*cur=head;
    while(cur)
    {
        struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
        struct Node* next=cur->next;

        cur->next=newnode;

        newnode->next=next;
        newnode->val=cur->val;

        cur=next;
    }
    //第二步
    cur=head;
    while(cur)
    {
        struct Node*prev=cur->next;
        if(cur->random==NULL)
        {
            prev->random=NULL;
        }
        else
        {
            prev->random=cur->random->next;
        }
        cur=cur->next->next;
    }
    //第三步
    struct Node* newhead=NULL,*newtail=NULL;
    cur=head;
    while(cur)
    {
        struct Node*prev=cur->next;
        struct Node*next=prev->next;
        if(newhead==NULL)
        {
            newhead=newtail=prev;
        }
        else
        {
            newtail->next=prev;
            newtail=prev;
        }
        cur=next;
    }
    return newhead;
}

总结

  链表的相关题目到这里就结束了,当然同学们也可以去oj看看其他题:oj题
  更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!

专栏订阅:
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!

【数据结构】链表相关题目(中档题),初阶数据结构,链表,数据结构,leetcode文章来源地址https://www.toymoban.com/news/detail-813943.html

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

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

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

相关文章

  • 初阶数据结构(三)链表

    💓博主csdn个人主页:小小unicorn💓 ⏩专栏分类:c++ 🚚代码仓库:小小unicorn的学习足迹🚚 🌹🌹🌹关注我带你学习编程知识 前面我们讲的线性表的 顺序存储结构 。它是有缺点的,最大的缺点就是插入和删除时需要移动大量元素,这显然就需要 耗费时间 ,那能不能想办法

    2024年02月09日
    浏览(60)
  • 【数据结构初阶】链表OJ

    OJ 方案一: 题目解析: 方案二: 题目解析:把原链表遍历一遍,插入新链表 OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: 定义快慢指针,使快指针先走与慢指针同步。然后同时走看是否相交 OJ 题目解析: OJ 题目解析:

    2024年02月05日
    浏览(50)
  • 数据结构——图解链表OJ题目

            学完了单链表之后,我们对其基本结构已经有了一定的了解,接下来我们通过一些题目强化对链表的理解,同时学习一些面试笔试题目的新思路以及加强对数据结构单链表的掌握。  目录 题目一.876. 链表的中间结点 - 力扣(LeetCode) 题目二:21. 合并两个有序链表

    2024年02月04日
    浏览(65)
  • 【数据结构初阶】第四节.链表详讲

    前言 一、单链表的概念 二、链表的创建 2.1链表的初始化 2.2 打印链表 2.3 获取链表的长度 2.4 判断链表是否为空 三、新增结点 3.1头插 3.2 指定下标插入 四、删除结点 4.1 头删 4.2 指定下标的删除 4.3 删除链表中的指定元素 五、单链表查找 六、附录 总代码 测试代码 总结 前

    2023年04月15日
    浏览(71)
  • 【数据结构初阶】顺序表和链表(1)

    线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月08日
    浏览(241)
  • 初阶数据结构之---顺序表和链表(C语言)

    线性表: 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构,也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时,通常以 数组 和 链式结构 的形式存储。

    2024年02月22日
    浏览(66)
  • 【数据结构初阶】四、线性表里的链表(带头+双向+循环 链表 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】三、 线性表里的链表(无头+单向+非循环链表 -- C语言实现)-CSDN博客  ====

    2024年02月08日
    浏览(44)
  • C/C++数据结构之链表题目答案与解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言  2.题目解析 2.1 移除链表元素 2.2反转链表 2.3链表的中

    2024年02月05日
    浏览(60)
  • 『初阶数据结构 • C语言』⑨ - 基于结点的数据结构——链表(单链表&&双向循环链表)附完整源码

      本章内容 1.什么是链表 2.链表常见几种形式 3.无头单向非循环链表的实现 3.1结点结构的定义 3.2函数接口的实现 3.2.1尾插 3.2.2尾删 4. 带头双向循环链表的实现 4.1结点结构的定义 4.2函数接口的实现 5.两种链表的差异 ①尾插与尾删的时间复杂度 ②头插与头删的时间复杂度 ③

    2024年02月16日
    浏览(81)
  • 【数据结构】二叉树的相关操作以及OJ题目

    当一个树不是满二叉树或完全二叉树时,它是不适合使用数组存储的,它应该使用链式结构来存储。 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因

    2024年03月19日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包