数据结构——单链表OJ题(第二弹)

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

数据结构——单链表OJ题(第二弹),数据结构,链表


前言

此次练习题有两道!
有点小难度,但相信难不住大家的!

我也会给出两道OJ题的链接,大家也赶快去试一试吧


一、返回链表开始入环的第一个节点

题目链接:OJ链接
数据结构——单链表OJ题(第二弹),数据结构,链表
数据结构——单链表OJ题(第二弹),数据结构,链表

提示:

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

本题有两个解析思路~
数据结构——单链表OJ题(第二弹),数据结构,链表
数据结构——单链表OJ题(第二弹),数据结构,链表

思路一

数据结构——单链表OJ题(第二弹),数据结构,链表
代码演示:

//解题方法一
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *move1=head;
    struct ListNode *move2=head;
    while(move1&&move2&&move2->next){//快慢指针移动
        move1=move1->next;
        move2=move2->next->next;
            if(move1==move2){{//找到相遇点
            struct ListNode *meet=move1;//meet从相遇点开始移动
            struct ListNode *move3=head;//move3从head开始移动
            while(meet!=move3){//两个指针同时移动找到起始点
                meet=meet->next;
                move3=move3->next;
            }
            return meet;
        }
    }
   
    return NULL;
}

思路二

数据结构——单链表OJ题(第二弹),数据结构,链表

提示:如果不了解如何找出公共点的的话,前面的博客会对大家有所帮助!
博客链接:单链表OJ题

代码演示:

//解题方法二
struct ListNode *detectCycle(struct ListNode *head) {
   struct ListNode *move1=head;
   struct ListNode *move2=head;
   while(move1&&move2&&move2->next){//快慢指针移动
        move1=move1->next;
        move2=move2->next->next;
        if(move1==move2){//找到相遇点
            struct ListNode *temp=move1;//保存相遇点位置
            move1=move1->next;//将move1变为第二链表起始点
            temp->next=NULL;//将相遇点的next置空
            struct ListNode *head1=head;
            struct ListNode *head2=move1;
            int len1=0,len2=0;
            while(head1!=NULL){//计算链表长度
                len1++;
                head1=head1->next;
            }
            while(head2!=NULL){
                head2=head2->next;
                len2++;
            }
            int k=abs(len1-len2);//得到两链表长度相减的绝对值
            //将longs指向较长的链表,shorts指向较短的链表
            struct ListNode *shorts=head;
            struct ListNode *longs=move1;
            if(len1>len2){
                shorts=move1;
                longs=head;
            }
            while(k--&&longs!=NULL){//较长的链表移动k位
                longs=longs->next;
            }
            if(k>0&&longs==NULL){
                return NULL;
            }
            while(shorts!=longs){//两链表同时遍历,找到第一个公共点
                shorts=shorts->next;
                longs=longs->next;
            }
            return longs;
         }
    }
    return NULL;
}

二、返回链表的深度拷贝

题目链接:OJ链接
数据结构——单链表OJ题(第二弹),数据结构,链表
数据结构——单链表OJ题(第二弹),数据结构,链表
数据结构——单链表OJ题(第二弹),数据结构,链表

提示:

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

解题思路:
数据结构——单链表OJ题(第二弹),数据结构,链表
数据结构——单链表OJ题(第二弹),数据结构,链表

代码演示

struct Node* BuyNewnode(int x){//创建结点函数
    struct Node*newnode=(struct Node*)malloc(sizeof(struct Node));
    newnode->val=x;
    newnode->next=NULL;
    newnode->random=NULL;
    return newnode;
}
//查找random所在位置的函数
struct Node* findrandom(struct Node* head,struct Node* newhead,struct Node* random){
    struct Node*move1=head;
    struct Node*move2=newhead;
    while(move1!=random){
        move1=move1->next;
        move2=move2->next;
    }
    return move2;
}

struct Node* copyRandomList(struct Node* head) {
	struct Node*move=head;
    struct Node*newhead=NULL;
    struct Node*tail=NULL;
    while(move!=NULL){//将新建结点依次尾插到新链表中
         if(tail==NULL){
            struct Node*newnode= BuyNewnode(move->val);
            newhead=tail=newnode;
            move=move->next;
         }
              else{
             struct Node*newnode= BuyNewnode(move->val);
             tail->next=newnode;
             tail=tail->next;
             move=move->next;
         }
    }
    struct Node*setran=newhead;
    struct Node*findran=head;
      while(setran&&findran){
        struct Node*temp=findrandom(head,newhead,findran->random);
        setran->random=temp;
        setran=setran->next;
        findran=findran->next;
    }
    return newhead;
}

总结

这次的题目稍稍有些难度!
但是绝对难不倒大家的!
加油! 加油!文章来源地址https://www.toymoban.com/news/detail-632151.html

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

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

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

相关文章

  • 【数据结构】单链表OJ题

    🔥 博客主页: 小王又困了 📚 系列专栏: 数据结构 🌟 人之为学,不日近则日退  ❤️ 感谢大家点赞👍收藏⭐评论✍️ 目录 一、移除链表元素 💡方法一: 💡方法二: 二、链表的中间节点 💡方法一: 三、链表中倒数第k个结点 💡方法一: 四、反转链表 💡方法一:

    2024年02月14日
    浏览(58)
  • 数据结构——单链表OJ题

    在前面的博客中我们知道了什么是单链表以及如何建立单链表! 现在让我们来检验一下学习成果吧! 提示:此博客中题目均来自牛客网以及力扣网!在题目中我会附带两大网站的链接,大家也可以去练习一下! 若有链接问题可以在评论区及时反馈! 题目链接: OJ链接 提示

    2024年02月14日
    浏览(82)
  • 【数据结构】单链表OJ题(一)

    🔥 博客主页: 小王又困了 📚 系列专栏: 数据结构 🌟 人之为学,不日近则日退  ❤️ 感谢大家点赞👍收藏⭐评论✍️ 目录 一、移除链表元素 💡方法一: 💡方法二: 二、链表的中间节点 💡方法一: 三、链表中倒数第k个结点 💡方法一: 四、反转链表 💡方法一:

    2024年02月13日
    浏览(80)
  • 【数据结构】单链表OJ题(二)

    🔥 博客主页: 小王又困了 📚 系列专栏: 数据结构 🌟 人之为学,不日近则日退  ❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、链表分割 💡方法一: 二、链表的回文 💡方法一:  三、相交链表 💡方法一:  四、环形链表  💡方法一:  🗒️前言: 在上一期中我们

    2024年02月14日
    浏览(40)
  • 【数据结构练习】单链表OJ题(二)

    题目: 示例: 注意:不能根据节点的值来比较是否相交,而是根据节点在内存中是否指向相同的位置。 例如以上图: 链表A:4、1、8、4、5 链表B:5、6、1、8、4、5 链表A和链表B都有节点的值为1,但是它们在内存中指向不同的位置,而值为8的节点(A的第三个节点、B的第四个

    2024年02月11日
    浏览(39)
  • 【数据结构练习】单链表OJ题(一)

    题目: 思路1: 在原来的链表上进行修改,节点的数据是val的删除,然后前后再连接起来。 需要考虑的因素: 1.要删除的节点位置在第一个节点; 2.要删除的节点位置在中间任意一个节点; 3.要删除的节点位置在最后一个节点 用一个变量cur遍历链表,要删除的节点是头节点

    2024年02月11日
    浏览(60)
  • 深入理解数据结构第二弹——二叉树(2)——堆排序及其时间复杂度

    看这篇前请先把我上一篇了解一下:深入理解数据结构第一弹——二叉树(1)——堆-CSDN博客 前言: 相信很多学习数据结构的人,都会遇到一种情况,就是明明最一开始学习就学习了时间复杂度,但是在后期自己写的程序或者是做到哪个需要判断时间复杂度的题时,仍然判

    2024年04月09日
    浏览(45)
  • 【LeetCode】【数据结构】单链表OJ常见题型(一)

     👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》 🌝 每一个不曾起舞的日子,都是对生命的辜负。 目录 前言: 【LeetCode】203.移除链表元素 【LeetCode】206.反转链表  思路一 思路二 【LeetCode】876.链表的中间结点 快慢指针法

    2024年02月14日
    浏览(37)
  • 【LeetCode】【数据结构】单链表OJ常见题型(二)

     👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言: 【LeetCode】面试题02.04. 分割链表 【LeetCode】160. 相交链表 【LeetCode】141. 环形链表 【LeetCode】142. 环形链表Ⅱ 方法

    2024年02月14日
    浏览(44)
  • 数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第二弹)

     朋友们、伙计们,我们又见面了,本期来给大家解读一下有关二叉树的经典例题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 ​ 目录   前言: 一、

    2024年02月10日
    浏览(87)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包