[C语言刷题篇]链表运用讲解

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

目录

NC25 删除有序链表中重复的元素-I

描述

方法一:遍历删除(推荐使用)

方法二:递归求解

反转链表

描述

解法:迭代


给大家推荐一款神器牛客网以下题型及方法牛客都有,及企业面试高频题

c语言链表应用,算法与数据结构,c语言,链表,数据结构

 文章来源地址https://www.toymoban.com/news/detail-568883.html

NC25 删除有序链表中重复的元素-I

描述

删除给出链表中的重复元素(链表中元素从小到大有序),使链表中的所有元素都只出现一次
例如:
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3.

数据范围:链表长度满足0≤n≤100,链表中任意节点的值满足val∣≤100

进阶:空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)

c语言链表应用,算法与数据结构,c语言,链表,数据结构

 我们可以在题目得到这样的信息:

  • 给定一个从小到大排好序的链表
  • 删去链表中重复的元素,每个值只留下一个节点

方法一:遍历删除(推荐使用)

思路:

既然连续相同的元素只留下一个,我们留下哪一个最好呢?当然是遇到的第一个元素了!

if(cur->val==cut->next->val)
    cur->var=cur->next->next;

因为第一个元素直接就与前面的链表节点连接好了,前面就不用管了,只需要跳过后面重复的元素,连接第一个不重复的元素就可以了,在链表中连接后面的元素总比连接前面的元素更方便嘛,因为不能逆序访问。

具体做法:

  • step 1:判断链表是否为空链表,空链表不处理直接返回。
  • step 2:使用一个指针遍历链表,如果指针当前节点与下一个节点的值相同,我们就跳过下一个节点,当前节点直接连接下个节点的后一位。
  • step 3:如果当前节点与下一个节点值不同,继续往后遍历。
  • step 4:循环过程中每次用到了两个节点值,要检查连续两个节点是否为空。

c语言链表应用,算法与数据结构,c语言,链表,数据结构

 

动图展示:c语言链表应用,算法与数据结构,c语言,链表,数据结构

 核心代码

struct ListNode* deleteDuplicates(struct ListNode* head ) {
    if(head == NULL || head->next == NULL) return head;
    struct ListNode *p=head,*pn = head->next;
    while(p){
        if(p->val == pn->val){
            while(pn&&pn->val == p->val) //判断
            pn = pn->next;
            p->next = pn;//删除
        }
        p = p->next;
        
    }
    return head;
    // write code here
}

 

复杂度分析:

  • 时间复杂度:O(n)O(n)O(n),其中nnn为链表长度,遍历一次链表
  • 空间复杂度:O(1)O(1)O(1),常数级指针变量使用,没有使用额外的辅助空间

方法二:递归求解


核心思想:
        采用递归的思想求解。每次递归则需要比较并删除重复的元素。本次的思想跟递归逆置链表很像,唯一的不同就是处理逻辑不同。删除重复链表的处理逻辑是每次都要删除当前节点(如果当前节点与下一个节点相同时候)

核心代码:

ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr)    //节点不存在或者只有一个节点时,递归结束
        return head;
    head->next = deleteDuplicates(head->next);      //递归体,每次递归从下一个节点开始
    if (head->val == head->next->val)     //比较当前元素和下一个元素的值是否相等,相等则直接删除当前节点
        head = head->next;            //head指针指向下一个节点,表明当前节点丢失,已经不再属于这个链表
    return head;                //返回本次递归的结果
}

复杂度分析:
        递归n次,因此时间复杂度为O(N)。而每次递归都需要一个额外的变量保存,因此空间复杂度为O(N),时间复杂度O(n)
 

反转链表

描述

给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。

数据范围:0≤n≤1000

要求:空间复杂度 O(1)O(1) ,时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时,

经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。

以上转换过程如下图所示:

c语言链表应用,算法与数据结构,c语言,链表,数据结构

 c语言链表应用,算法与数据结构,c语言,链表,数据结构

 

解法:迭代

  • 在遍历链表时,将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。
  • 图解:c语言链表应用,算法与数据结构,c语言,链表,数据结构

 

复杂度分析:

时间复杂度:O(N),其中 N 是链表的长度。需要遍历链表一次。

空间复杂度:O(1),常数空间复杂度

代码展示:

```/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */

struct ListNode* ReverseList(struct ListNode* pHead ) {
    if(!pHead)return NULL;
    if(pHead->next==NULL)return pHead;
    struct ListNode *p,*t;
    t=pHead->next;
    p=pHead;p->next=NULL;
    while(t){
        p=t;
        t=t->next;
        p->next=pHead;
        pHead=p;
    }
    return p;
}

点击右边链接牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推,求职就业一站解决_牛客网

c语言链表应用,算法与数据结构,c语言,链表,数据结构

 

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

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

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

相关文章

  • 【刷题篇】贪心算法(一)

    假设1元、2元、5元、10元、20元、50元、100元的纸币分别由c0,c1,c2,c3,c4,c5,c6张。现在要用这些钱来支付K元,至少要用多少张纸币?

    2024年02月09日
    浏览(45)
  • 【刷题篇】贪心算法

    假设1元、2元、5元、10元、20元、50元、100元的纸币分别由c0,c1,c2,c3,c4,c5,c6张。现在要用这些钱来支付K元,至少要用多少张纸币?

    2024年02月09日
    浏览(37)
  • 【C语言】字符串---刷题篇

    Hi,C站的小伙伴们大家好呀!😊🥰,欢迎来阅读我的这一篇 【C语言】字符串基础刷题篇! 不知你是否和我一样,在刚刚接触到这块的知识时,总是会和这神圣的知识隔着隔着厚厚的一堵墙,迷茫的眼神中总是会露出不理解不理解😣😣(当时的状态……) 其实后来我就发现其实

    2024年02月03日
    浏览(44)
  • 【C语言编程之旅 1】刷题篇-初识c语言

    C语言中内置类型包括: char //字符数据类型 short //短整型 int //整形 long //长整型 long long //更长的整形 float //单精度浮点数 double //双精度浮点数 struct是用户用来自定义的结构体类型,不属于C语言的内置类型。 因此:选择C

    2024年01月17日
    浏览(55)
  • C语言数据结构(链表概念讲解和插入操作)

    本篇文章带大家正式的来学习数据结构,数据结构是学习操作系统,和深入C语言必不可少的,所以这篇文章开始带大家学习数据结构的知识。 链表(Linked List)是一种常见的数据结构,用于存储和组织数据元素。它由一系列节点(Node)组成,每个节点包含存储的数据(或称

    2024年02月06日
    浏览(37)
  • 【C语言编程之旅 6】刷题篇-for循环

    思路: 两个循环进行控制 外层循环控制打印多少行 内部循环控制每行打印多少个表达式以及表达式内容, 比较简单,具体参考代码 思路: 采用循环的方式输入一个数组 使用max标记数组中的最大值,采用循环的方式依次获取数组中的每个元素,与max进行比较,如果arr[i]大于

    2024年01月21日
    浏览(44)
  • C语言编程入门之刷题篇(C语言130题)(8)

    (题目标题可以直接跳转此题链接) BC72 平均身高   从键盘输入5个人的身高(米),求他们的平均身高(米)。 输入描述: 一行,连续输入5个身高(范围0.00~2.00),用空格分隔。 输出描述: 一行,输出平均身高,保留两位小数。 输入:1.68 1.75 1.82 1.60 1.92 输出:1.75  参考

    2024年02月02日
    浏览(35)
  • 【LeetCode刷题篇零】一些基础算法知识和前置技能(上)

    冒泡排序 冒泡的核心是两两比较,大数下沉,小数上浮,比较的轮数是数组的长度 N,每一轮比较的次数为 N - 当前轮的索引: 外层循环控制轮数 round: [1,N] 内层循环控制次数 i: [0,N - round) 在每一轮当中,内循环中两两比较相邻的两个数,大数下沉(交换),如果某一轮没

    2024年02月07日
    浏览(46)
  • DSt:数据结构的最强学习路线之数据结构知识讲解与刷题平台、刷题集合、问题为导向的十大类刷题算法(数组和字符串、栈和队列、二叉树、堆实现、图、哈希表、排序和搜索、动态规划/回溯法/递归/贪心/分治)总

    Algorithm:【算法进阶之路】之算法面试刷题集合—数据结构知识和算法刷题及其平台、问题为导向的十大类刷题算法(数组和字符串、链表、栈和队列、二叉树、堆、图、哈希表、排序和搜索、回溯算法、枚举/递归/分治/动态规划/贪心算法)总结 目录 相关文章

    2024年02月08日
    浏览(56)
  • 【数据结构和算法初阶(C语言)】复杂链表(随机指针,随机链表的复制)题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题: 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(87)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包