【数据结构】单链表OJ题

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

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

🔥博客主页:小王又困了

📚系列专栏:数据结构

🌟人之为学,不日近则日退 

❤️感谢大家点赞👍收藏⭐评论✍️


目录

一、移除链表元素

💡方法一:

💡方法二:

二、链表的中间节点

💡方法一:

三、链表中倒数第k个结点

💡方法一:

四、反转链表

💡方法一:

💡方法二:

五、合并两个有序链表

💡方法一: 


🗒️前言:

在上一期中我们给大家介绍了单链表,也了解了单链表的实现。接下来就让我们进入实践,练习一些经典题目,让我们对单链表的理解更加深入。

一、移除链表元素

题目:

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

💡方法一:

我们使用两个指针遍历数组,遇到与 val 相同的数据域,就删除这个节点。我们在思考问题时要想全面,当要删除头节点时,常规方法就无法实现,对于删除头节点要做单独处理。

🍩常规删除: 

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

 🍩头节点删除

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev=NULL;
    struct ListNode* cur=head;
    while(cur!=NULL)
    {
        //删除
        if(val==cur->val)
        {
            //头删
            if(cur==head)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            //常规
            else
            {
                prev->next=cur->next;
                free(cur);
                cur=prev->next;
            }
        }

        //遍历
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

💡方法二:

我们通过遍历,把节点的数据域不等于val的节点尾接到新的链表中。我们要考虑第一个节点是不是要删除的。最后一个节点的指针域置空要放在循环结束后,判断tail是否为空指针。

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* newhead=NULL;
    struct ListNode* tail=NULL;
    struct ListNode* cur=head;
    while(cur)
    {
        if(cur->next==val)
        {
            //删除
            struct ListNode* del=cur;
            cur=cur->next;
            free(del);
        }
        else
        {
            //尾插
            if(tail==NULL)
            {
                newhead=tail=cur;
                //tail=cur;
            }
            else
            {
                tail->next=cur;
                tail=tail->next;   
            }
            cur=cur->next;
        }
    }
    if(tail)
    {
        tail->next=NULL;
    }
    return newhead;
}

二、链表的中间节点

题目:

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

💡方法一:

我们可以定义两个指针,快指针一次走两步,慢指针一次走一步,当快指针走到结尾时,慢指针正好走了一半,这样我们就可以找到中间节点。

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

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

三、链表中倒数第k个结点

题目:

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

💡方法一:

我们可以参考上一题的方法,同样定义快慢指针,想让快指针走k步,然后在同时走,走到fast为空指针就找了倒数第k个节点。有可能链表没有k个节点,所以我们要加入判断。

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
       struct ListNode* fast=pListHead;
       struct ListNode* slow=pListHead;
        while(k--)
        {
            //链表没有k步长
            if(fast==NULL)
            {
                return NULL;
            }
            fast=fast->next;
        }
       while(fast!=NULL)
       {
            fast=fast->next;
            slow=slow->next;
       }
    return slow;
}

四、反转链表

题目:

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

💡方法一:

我们定义三个指针n1,n2,n3,来改变节点链接的顺序。将头节点变为尾节点,当n2为空指针时,n1就为链表的头节点,只需返回n1就可以。两个指针倒方向,一个指针保持下一个。

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* n1=NULL;
    struct ListNode* n2=head;
    struct ListNode* n3;
    if(n2)
    {
        n3=n2->next;
    }
    while(n2)
    {
        n2->next=n1;
        
        //往后走
        n1=n2;
        n2=n3;
        if(n3)
        {
            n3=n3->next;
        }
    }
    return n1;
}

💡方法二:

将链表的节点一个一个拿下来,进行头插。这里要注意赋值的顺序。

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur=head;
    struct ListNode* newnode=NULL;
    while(cur)
    {
        //保存节点
        struct ListNode* next=cur->next;

        //头插
        cur->next=newnode;
        newnode=cur;
        cur=next;
    }
    return newnode;
}

五、合并两个有序链表

题目:

【数据结构】单链表OJ题,数据结构,链表,数据结构,c语言,c++,算法

💡方法一: 

我们创建一个带哨兵位的链表,这样在尾插时就不用判断是否是第一个节点,可以提高效率。要记住在最后要将哨兵位的空间释放。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1==NULL)
    {
        return list2;
    }


    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode* head=NULL;
    struct ListNode* tail=NULL;
    //创建一个哨兵位
    head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            tail->next=list1;
            tail=tail->next;
            list1=list1->next;
        }
        else
        {
            tail->next=list2;
            tail=tail->next;
            list2=list2->next;
        }
    }
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    struct ListNode* del=head;
    head=head->next;
    free(del);
    return head;
}

本次的内容到这里就结束啦。希望大家阅读完可以有所收获,同时也感谢各位读者三连支持。文章有问题可以在评论区留言,博主一定认真认真修改,以后写出更好的文章。你们的支持就是博主最大的动力。文章来源地址https://www.toymoban.com/news/detail-627873.html

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

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

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

相关文章

  • 【数据结构与算法】:10道链表经典OJ

    思路1:遍历原链表,将 val 所在的节点释放掉。(太麻烦) 思路2:创建新链表,再遍历原链表,找到不为 val 的节点尾插到新链表。 思路1代码实现如下: 注意: 1.当链表为空时,直接返回NULL即可。 2.当尾插上最后一个有效节点时,此时它的 next 可能还与最后一个节点相链接,

    2024年04月14日
    浏览(36)
  • (c语言实现)数据结构链表oj题(2)

    🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介::分析力扣中有关链表的部分题目. 题目来源于:牛客网-题目链接 输入一个链表,输出该链表中倒数第k个结点。 示例: 输入:1,{1,2,3,4,5} 返回值:{5} 创建两个指针: ①

    2024年02月04日
    浏览(53)
  • 【数据结构】链表OJ题(顺序表)(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年02月05日
    浏览(43)
  • [C语言][数据结构][链表] 单链表的从零实现!

    目录 零.必备知识 1.一级指针 二级指针 2. 节点的成员列表     a.数据     b.指向下一个节点的指针. 3. 动态内存空间的开辟 (malloc-calloc-realloc) 一.单链表的实现与销毁          1.1 节点的定义         1.2 单链表的尾插         1.3 单链表的头插         1.4 单链表的尾删  

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

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

    2024年02月16日
    浏览(78)
  • 【数据结构与算法】一套链表 OJ 带你轻松玩转链表

    ✨个人主页:bit me ✨当前专栏:数据结构 ✨刷题专栏:基础算法   简介: 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 示例1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例2: 输入:head = [], val =

    2024年01月22日
    浏览(45)
  • 【数据结构与算法】顺序表与链表(单链表和双链表)超详解图示与源码。

                                                       大家好,今天我们来学习数据结构中的顺序表与链表!源码在最后附上 首先我们先来认识一下 顺序表 :                                       **如上图所示:很多人会以为数组就是顺序表,顺序表就是数组,这

    2024年02月21日
    浏览(55)
  • 数据结构--单链表OJ题

    上文回顾---单链表 这章将来做 一些链表的相关 题目 。 目录 1.移除链表元素 2.反转链表 3.链表的中间结点 4.链表中的倒数第k个结点 5.合并两个有序链表 6.链表分割 7.链表的回文结构 8.相交链表 9.环形链表 ​编辑  10.环形链表II ​编辑 ​编辑    思路:我们可以 通过循环链

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

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

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

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

    2024年02月14日
    浏览(82)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包