C语言单链表OJ题(较易)

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

一、移除链表元素

leetcode链接

题目描述:

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

C语言单链表OJ题(较易),数据结构,C语言,C语言/C++练习题,c语言,算法,数据结构

思路:

正常遍历,找到value的值与题目中相同的结点去free掉,分为两种情况:

第一种就是头结点就是value值,直接将头节点指向next;

第二种情况就是第二个结点开始是value,需要有一个前结点指向value结点的下一个。

源码:

struct ListNode* removeElements(struct ListNode* head, int val)
{
    //链表本身为空
    if(head==NULL)
        return NULL;
    struct ListNode* prev = NULL;
    while(1)//头节点开始就是值
    {
        if(head->val==val)
        {
            prev=head;
            head=head->next;
            free(prev);
            if(head==NULL)
            {
                return NULL;
            }
        }
        else
        {
            break;
        }
    }
    struct ListNode* cur = head;
    while(cur)//从第二个开始才是value,可以使用prev,因为第一个不是value,可以存储
    {
        //这一部分卡了好久
        if(cur->val==val)
        {
            prev->next=cur->next;    
            struct ListNode* del=cur;
            free(del);
            cur=prev->next;
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

C语言单链表OJ题(较易),数据结构,C语言,C语言/C++练习题,c语言,算法,数据结构

二、链表的中间结点

leetcode链接

题目描述:

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

C语言单链表OJ题(较易),数据结构,C语言,C语言/C++练习题,c语言,算法,数据结构

思路:

快慢指针法

进行一个循环,先让快指针走两步,然后让慢指针走一步,直到快指针指向空或者快指针的next指向空,这时候的慢指针就指向了中间结点,并且也满足第二个结点。

代码:

struct ListNode* middleNode(struct ListNode* head)
{
    //快慢指针,快指针走两步,慢指针走一步
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

C语言单链表OJ题(较易),数据结构,C语言,C语言/C++练习题,c语言,算法,数据结构

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

牛客网链接

题目描述:

输入一个链表,输出该链表中倒数第k个结点。

C语言单链表OJ题(较易),数据结构,C语言,C语言/C++练习题,c语言,算法,数据结构

思路:

也是快慢指针的思想。

先让快指针走k步,然后再让快指针和慢指针一起走,直到快指针为空

这题有一些注意细节的点,比如k大于链表结点的个数,k==0,但这些都是小细节,主要思想还是快慢指针~

C语言单链表OJ题(较易),数据结构,C语言,C语言/C++练习题,c语言,算法,数据结构 代码:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    if(pListHead==NULL||k==0)//k=0和链表为空的情况
    {
        return NULL;
    }
    struct ListNode* fast=pListHead;
    struct ListNode* slow=pListHead;
    while(k--)//先让快指针走k步
    {
        fast=fast->next;
        if(fast==NULL)
        {
            break;
        }
    }
    if(k>0)//k大于链表结点的个数的情况
    {
        return NULL;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

四、反转链表

leetcode链接

题目描述:

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

C语言单链表OJ题(较易),数据结构,C语言,C语言/C++练习题,c语言,算法,数据结构

思路:

顺序遍历链表,从第一个结点开始进行尾插,注意这里的尾插不是手撕单链表里面的pushback函数,而是应该将结点一个一个取下来。

相当于我们又学习了另外一种尾插的方式,不是直接改变头节点的值,而是将原有的头节点指向新的头节点。

代码:

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead=NULL;
    struct ListNode* next=NULL;
    //头插
    while(head)
    {
        next=head->next;
        head->next=newhead;
        newhead=head;
        head=next;
    }
    return newhead;
}

C语言单链表OJ题(较易),数据结构,C语言,C语言/C++练习题,c语言,算法,数据结构

 五、合并两个有序链表

leetcode链接

题目描述:

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

C语言单链表OJ题(较易),数据结构,C语言,C语言/C++练习题,c语言,算法,数据结构

思路:

两个链表的第一个结点顺序比较,取小的尾插到一个新的头结点上,若一个提前结束,则将另一个直接尾插到新链表上

代码:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    //取小的尾插
    //为何这题可以直接定义一个尾结点?
    struct ListNode* newhead=NULL;
    struct ListNode* tail=NULL;
    while(list1 && list2)
    {
        if(list1->val <= list2->val)
        {
            if(newhead==NULL)
            {
                newhead=tail=list1;
                //tail=newhead->next;
            }
            else
            {
                tail->next=list1;
                //tail=list1->next;
                tail=tail->next;
            }
            list1=list1->next;
        }
        else
        {
            if(newhead==NULL)
            {
                tail=newhead=list2;
                //tail=newhead->next;
            }
            else
            {
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next;
        }
    } 
    if(list1)//剩余直接尾插
    {
        //tail=list1;
        tail->next=list1;
    }  
    if(list2)
    {
        //tail=list2;
        tail->next=list2;
    }
    return newhead;
}    

小心得:

在数据结构的新篇章里,注意的小细节更多,最好将能考虑的情况都要考虑到,不然调试起来比较麻烦。一般只有将头结点为空的情况下,直接赋值等于,其余一般都需要进行next链接。文章来源地址https://www.toymoban.com/news/detail-628320.html

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

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

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

相关文章

  • 数据结构--单链表OJ题

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

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

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

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

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

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

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

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

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

    2024年02月13日
    浏览(79)
  • 数据结构——单链表OJ题(第二弹)

    此次练习题有两道! 有点小难度,但相信难不住大家的! 我也会给出两道OJ题的链接,大家也赶快去试一试吧 题目链接: OJ链接 提示: 链表中节点的数目范围在范围 [0, 104] 内 -105 = Node.val = 105 pos 的值为 -1 或者链表中的一个有效索引 本题有两个解析思路~ 代码演示: 提示:

    2024年02月14日
    浏览(39)
  • 【数据结构练习】单链表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)
  • 【LeetCode】【数据结构】单链表OJ常见题型(二)

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

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

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

    2024年02月14日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包