C语言简单的数据结构:单链表的有关算法题(2)

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


接着我们介绍后面的三道题,虽然代码变多了但我们的思路更加通顺了

4. 单链表相关经典算法OJ题3:合并两个有序链表

题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
创建新链表,遍历原链表,将节点值小的进行尾插到新链表中
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
这里要多次进行对NULL的判断,开始传入列表,中间newHead的判断,循环出来一个为NULL的判断
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
重复原因:新链表存在空链表和非空两种情况
优化的方法:
1.将重复的部分封装成一个函数
2.动态申请一个空间但这个空间部存储任何的信息
那么我们着重讲一下第二个方法:
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法

他的解决方法就是让新链表不为NULL
在创建时动态申请一块空间,但不存储任何数据,让NULL节点变为非NULL的节点,这是就不用判断链表是不是为非NULL
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法

但这时返回就不能将头节点直接返回,而是要将头节点的下一个位置的地址返回
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
当然释放的空间还是要释放一下,来使代码更加完善
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* l1 = list1;
    ListNode* l2 = list2;
    //判空
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }

    ListNode* newHead,*newTail;
    //newHead = newTail = NULL;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
    
    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            newTail->next = l1;
            newTail = newTail->next;
            l1 = l1->next;
        }
        else
        {
            newTail->next = l2;
            newTail = newTail->next;
            l2 = l2->next;
        }
    }
    //跳出循环有两种情况
    if(l2 != NULL)
    {
        newTail->next = l2;
    }
    if(l1 != NULL)
    {
        newTail->next = l1;
    }
    ListNode* ret = newHead->next;
    free(newHead);
    newHead = NULL;
    return ret;
}

其实这样的链表叫带头链表,这个“头”一般称作哨兵位

5. 循环链表经典应⽤-环形链表的约瑟夫问题

题目链接:https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
思路一:用数组的方法,先进行遍历然后将离开的人置为0,然后不断循环遍历最中不为0的就是我们要的数据
思路二:循环链表的方法
我们先介绍一下循环链表:
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
这里涉及到循环链表,其实也就是单链表但是尾部相连了
那么在创建和删除时要多注意就行了
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
循环数数,将数到2的,将其删除
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法

这里就要使用前后指针
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
代码的难点就是创建循环链表

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
 #include <stdio.h>
typedef struct ListNode ListNode ;
 ListNode* buyNode(int x)//申请空间
 {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if(node == NULL)
    {
        exit(1);
    }
    node->val = x;
    node->next = NULL;
    return node;
 }

 ListNode* createCircle(int n)//创建带环链表
 {
    //创建第一个节点
    ListNode* phead = buyNode(1);
    ListNode* ptail = phead;
    for(int i = 2; i <= n;i++)
    {
        ptail->next = buyNode(i);
        ptail = ptail->next;
    }
    ptail->next = phead;
    return ptail;
 }
int ysf(int n, int m ) {
    // write code here
    ListNode* prev = createCircle(n);
    ListNode* pcur = prev->next;
    int count = 1;
    while (prev->next != pcur)//链表只有一个节点 
    {
        if(count == m)
        {
            //销毁,先连接,在销毁
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;
        }
        else 
        {
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    return pcur->val;
}

6. 单链表相关经典算法OJ题5:分割链表

题目链接:https://leetcode.cn/problems/partition-list-lcci/description/
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
思路一:将原列表复制一份,然后对大于等于x的进行操作,先尾插后销毁
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
思路二:或者创建一个新链表进行存储,对大于的数进行尾插,小于的进行头插
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
思路三:创建两个新链表:小链表和大链表
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
分成两个链表然后将两个链表连接起来
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
这里就是greaterHead后的指针不为NULL,而是一个随机地址
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法
将两个代码换过来,就可以解决这个问题了
C语言简单的数据结构:单链表的有关算法题(2),c语言,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-852492.html

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL)
    {
        return head;
    }
    ListNode* lessHead,*lessTail;
    ListNode* greaterHead,*greaterTail;
    lessHead = lessTail =(ListNode*)malloc(sizeof(ListNode));
    greaterHead = greaterTail =(ListNode*)malloc(sizeof(ListNode));

    //遍历原链表,进行尾插
    ListNode* pcur = head;
    while(pcur)
    {
        if(pcur->val < x)
        {
            //小链表
            lessTail->next = pcur;
            lessTail = lessTail->next;
        }
        else
        {
            greaterTail->next =pcur;
            greaterTail = greaterTail->next;
        }
        pcur = pcur->next;
    }
    //首尾相连
    greaterTail->next = NULL;
    lessTail->next = greaterHead->next;
    

    ListNode* ret = lessHead->next;
    free(lessHead);
    free(greaterHead);
    lessHead = greaterHead = NULL;
    return ret;
}

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

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

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

相关文章

  • 【数据结构】C语言实现单链表的基本操作

    大家好,很高兴又和大家见面啦!!! 在上一篇中,我们详细介绍了单链表的两种创建方式——头插法与尾插法,相信大家现在对这两种方式都已经掌握了。今天咱们将继续介绍单链表的基本操作——查找、插入与删除。在开始今天的内容之前,我们先通过尾插法创建一个单

    2024年02月03日
    浏览(62)
  • 【数据结构】单链表的增删查改(C语言实现)

    在上一节中我们提到了顺序表有如下缺陷: 在头部/中间的插入与删除需要挪动数据,时间复杂度为O(N),效率低; 增容需要申请新空间,可能会拷贝数据,释放旧空间,会有不小的消耗; 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容

    2024年02月06日
    浏览(55)
  • 【数据结构】单链表的基本操作 (C语言版)

    目录 一、单链表 1、单链表的定义: 2、单链表的优缺点: 二、单链表的基本操作算法(C语言) 1、宏定义 2、创建结构体 3、初始化 4、插入 4、求长度 5、清空 6、销毁  7、取值 8、查找 9、删除 10、头插法创建单链表 11、尾插法创建单链表 三、单链表的全部代码(C语言)

    2024年01月22日
    浏览(56)
  • 【数据结构】 循环单链表的基本操作 (C语言版)

    目录 一、循环单链表 1、循环单链表的定义: 2、循环单链表的优缺点: 二、循环单链表的基本操作算法(C语言)    1、宏定义  2、创建结构体 3、循环单链表的初始化  4、循环单链表的插入 5、求单链表长度 6、循环单链表的清空 7、循环单链表的销毁 8、循环单链表的取

    2024年01月22日
    浏览(55)
  • 数据结构——单链表的查找、求单链表长度、单链表的创建

    一、单链表的查找 1.按位查找 ==GetElem(L, i): == 按位查找操作,获取表 L 中第 i 个位置的元素的值 ;   平均时间复杂度O(n) 2.按值查找 ==LocateElem(L, e)==: 按值查找操作,在表 L 中查找具有给定值的元素 ; 二、求单链表的长度 == Length(LinkList L)== :计算单链表中数据结点(

    2024年01月21日
    浏览(51)
  • 【(数据结构)— 单链表的实现】

    概念: 链表是⼀种 物理存储结构上非连续、 非顺序的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 。 链表的结构跟⽕⻋⻋厢相似,淡季时⻋次的⻋厢会相应减少,旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上,不会影响

    2024年02月08日
    浏览(48)
  • 【数据结构】单链表的实现

    🌇个人主页:平凡的小苏 📚学习格言:别人可以拷贝我的模式,但不能拷贝我不断往前的激情 🛸C语言专栏:https://blog.csdn.net/vhhhbb/category_12174730.html 🚀数据结构专栏:https://blog.csdn.net/vhhhbb/category_12211053.html         家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我

    2023年04月09日
    浏览(62)
  • 【数据结构】-- 单链表的实现

    在前面我们学习了顺序表,顺序表在数组的基础上提供了很多现成的方法,方便了我们对数据的管理,但是我们也发现顺序表有着许多不足: 在处理大型的数据时,需要频繁的增容且在中间删除或插入数据时需要遍历顺序表,这些性质导致了顺序表的 效率较低 。这时我们就

    2024年04月27日
    浏览(48)
  • 【数据结构—单链表的实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 1. 链表的概念及结构 2. 单链表的实现 2.1单链表头文件——功能函数的定义 2.2单链表源文件——功能函数的实现 2.3 单链表源文件——功能的测试 3.具体的理解操作图 4. 链表的分类 总结 世上

    2024年02月05日
    浏览(62)
  • 数据结构--单链表的定义

    单链表的定义(如何用代码实现) 优点:不要求大片连续空间,改变容量方便 缺点:不可随机存取,要耗费一定空间存放指针 为了方便 我们经常使用 typedef t y p e d e f 数据类型 别名 color{purple}typedef 数据类型 别名 t y p e d e f 数据类型 别名 代码一: 代码二: 代码一与代码二是

    2024年02月11日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包