LeetCode(2)合并链表、环形链表的约瑟夫问题、链表分割

一、合并链表

. - 力扣(LeetCode)

题目描述:

/**
 * 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) {
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }//如果list1开始是空,则返回list2,反之则返回list1;当两者都为空时,先走第一个if语句那么返回list2,list2为NULL。这样写包含了所有两者中有NULL的情况

    ListNode* newhead;
    ListNode* newtail;
    newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
    if (newhead == NULL)
    {
        perror("malloc fail!");
        exit(1);
    }//创建哨兵位

    ListNode* l1 = list1;
    ListNode* l2 = list2;

    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;
        }
    }
    //从l1、l2开始遍历,比较相应的val值,哪个小就把这个小的节点往哨兵位后面尾插

    if (l2)
    {
        newtail->next = l2;
    }
    if (l1)
    {
        newtail->next = l1;
    }//遍历两个链表时,会有一方先为空,另外一个不为空的的剩余的节点的val值都比新链表里面的小,并且list1、2都是升序,所以此时直接把没有插完的剩余的链表尾插到新链表的尾节点后面

    ListNode* rsl = newhead->next;
    free(newhead);
    newhead = NULL;
    return rsl;
    //动态开辟的空间要释放,但是也要依靠这个开辟的节点来返回,所以定义一个临时节点,释放完开辟的节点,将这个临时节点作为返回值。
}

 

二、环形链表的约瑟夫问题

环形链表的约瑟夫问题_牛客题霸_牛客网

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
typedef struct ListNode ListNode;
//申请节点
ListNode* BuyNode(int x)
{
    ListNode* newnode=(ListNode*)malloc(sizeof(ListNode));
    if(newnode==NULL)
    {
        exit(1);
    }
    newnode->next=NULL;
    newnode->val=x;
    return newnode;
}
#include <stdarg.h>
int ysf(int n, int m ) {
    // write code here
    ListNode* tail;
    ListNode* head;
    tail=head=(ListNode*)malloc(sizeof(ListNode));
    if(head==NULL)
    {
        exit(1);
    }
    head->next=NULL;
    head->val=1;//设置头节点(1<=n)
    for(int i=2;i<=n;i++)
    {
        ListNode* newnode=BuyNode(i);
        tail->next=newnode;
        tail=tail->next;
    }//创建一个链表

    //创建环形链表
    tail->next=head;

    ListNode* pcur=head;
    ListNode* prev=tail;
    int count=1;

    while(pcur->next!=pcur)
    {
        if(count!=m)
        {
            pcur=pcur->next;
            prev=prev->next;
            count++;
        }
        else
        {
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;
        }
    }

    return pcur->val;
}

while循环内部解释:假设n=5,m=2;最开始让pcur指向val为1的节点,让prev指向val为5的节点,设置一个计数器count,让其最开始的默认值是1;用count来记录pcur的走的步数(也就是报数为几),m为2,则先走if语句,此时pcur和prev都往后走一步,pcur指向2,prev指向1,count变为2(报数为2)要开始删除数据;则第二次循环进入else语句:开始删除数据,但是为了找到之后的链表节点,先让prev的next指针指向pcur的next指向的节点,再删除pcur(此时是2,符合题意,报数为2的删除)再让pcur为prev->next

此时prev的val为1,pcur的val为3,count重置为1(与题中当删除数据之后要从这个被删除数据的下一个数据重新开始计数);此时循环进入if语句,count变为2(正常报数),prev的val为3,pcur的val为4;再一次循环进入else语句,开始删除数据让prev的next指向pcur的next(也就是val为5的节点),再删除pcur(val为4的节点),让pcur为prev的next;此时pcur的val为5,prev的val为3,count重置为1;

依次类推;最后只剩下val为3的节点,并且此时pcur的next指向的就是它自己,返回这个val值就是最终结果。


三、分割链表

. - 力扣(LeetCode)

 

/**
 * 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 NULL;
    }

    ListNode* lesshead;
    ListNode* lesstail;
    lesshead=lesstail=(ListNode*)malloc(sizeof(ListNode));

    ListNode* morehead;
    ListNode* moretail;
    morehead=moretail=(ListNode*)malloc(sizeof(ListNode));
    if(lesshead==NULL || morehead==NULL)
    {
        exit(1);
    }
    ListNode* pcur=head;
    while(pcur)
    {
        if(pcur->val<x)
        {
            lesstail->next=pcur;
            lesstail=lesstail->next;
        }
        else
        {
            moretail->next=pcur;
            moretail=moretail->next;
        }
        pcur=pcur->next;
    }

    moretail->next=NULL;
    lesstail->next=morehead->next;
    

    ListNode* rsl=lesshead->next;
    free(morehead);
    free(lesshead);
    morehead=NULL;
    lesshead=NULL;
    
    return rsl;
}

 思路:创造两个新的链表,一个存储val比x小的节点,一个存储val比x大的节点,遍历原链表根据val的大小对新的两个链表进行尾插;结束之后要把这两个链表连起来,让存储较小值的链表在前面,但是这个链表不包含哨兵位,所以要让  lesstail->next=morehead->next;  最终释放这两个动态开辟的节点,返回合并链表的头节点。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/790184.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

选择最佳工具:评估8款顶级App界面设计软件

在如今的数字化时代&#xff0c;设计师也离不开各种界面设计软件来辅助自己的设计工作。在各种界面设计软件的帮助下&#xff0c;设计师们能够更好、更快地完成自己的设计工作。而今天本文要为大家推荐的这 8 款界面设计软件&#xff0c;分别是国产APP界面设计软件、Figma、Ske…

【数据库】Redis主从复制、哨兵模式、集群

目录 一、Redis的主从复制 1.1 主从复制的架构 1.2 主从复制的作用 1.3 注意事项 1.4 主从复制用到的命令 1.5 主从复制流程 1.6 主从复制实现 1.7 结束主从复制 1.8 主从复制优化配置 二、哨兵模式 2.1 哨兵模式原理 2.2 哨兵的三个定时任务 2.3 哨兵的结构 2.4 哨…

校园外卖系统带万字文档在线外卖管理系统java项目java课程设计java毕业设计

文章目录 校园外卖系统一、项目演示二、项目介绍三、万字项目文档四、部分功能截图五、部分代码展示六、底部获取项目源码带万字文档&#xff08;9.9&#xffe5;带走&#xff09; 校园外卖系统 一、项目演示 校园外卖服务系统 二、项目介绍 语言&#xff1a;java 数据库&…

ARM功耗管理标准接口之ACPI

安全之安全(security)博客目录导读 思考&#xff1a;功耗管理有哪些标准接口&#xff1f;ACPI&PSCI&SCMI&#xff1f; Advanced Configuration and Power Interface Power State Coordination Interface System Control and Management Interface ACPI可以被理解为一…

2023年高教杯数学建模2023B题解析(仅从代码角度出发)

前言 最近博主正在和队友准备九月的数学建模,在做往年的题目&#xff0c;博主主要是负责数据处理&#xff0c;运算以及可视化&#xff0c;这里分享一下自己部分的工作,相关题目以及下面所涉及的代码后续我会作为资源上传 问题求解 第一题 第一题的思路主要如下&#xff1a;…

单链表--续(C语言详细版)

2.6 在指定位置之前插入数据 // 在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); 分为两种情况&#xff1a;1. 插入的数据在链表中间&#xff1b;2. 插入的数据在链表的前面。 // 在指定位置之前插入数据 void SLTInsert(SLTNode** …

TISAX认证是什么?

TISAX认证是一种针对汽车行业数据安全和隐私保护的评估认证&#xff0c;其全称在不同资料中有所差异&#xff0c;但普遍认可的是它作为汽车行业信息安全评估体系的重要性。以下是对TISAX认证的详细解读&#xff1a; 一、背景和目的 随着汽车技术的不断发展&#xff0c;汽车数…

MySQL—统计函数和数学函数以及GROUP BY配合HAVING

合计/统计函数 count -- 演示 mysql 的统计函数的使用 -- 统计一个班级共有多少学生&#xff1f; SELECT COUNT(*) FROM student -- 统计数学成绩大于 90 的学生有多少个&#xff1f; SELECT COUNT(*) FROM student WHERE math > 90 -- 统计总分大于 250 的人数有多少&…

git-工作场景

1. 远程分支为准 强制切换到远程分支并忽略本地未提交的修改 git fetch origin # 获取最新的远程分支信息 git reset --hard origin/feature_server_env_debug_20240604 # 强制切换到远程分支&#xff0c;并忽略本地修改 2. 切换分支 1. **查看所有分支&#xff1a;**…

NewStarCTF2023-Misc

目录 week1 CyberChefs Secret 机密图片 流量&#xff01;鲨鱼&#xff01; 压缩包们 空白格 隐秘的眼睛 week2 新建Word文档 永不消逝的电波 1-序章 base! WebShell的利用 Jvav week3 阳光开朗大男孩 大怨种 2-分析 键盘侠 滴滴滴 week4 通大残 Nmap 依…

buuctf被嗅探的流量

下载出来是一个流量分析题 因为题目说了是联网状态下 嗅探到 所以一定有http协议 这里设置过滤器 一个一个去找吧 目前感觉wireshark的题都是http,太难的也不会

最后纪元Last Epoch可以通过什么搬砖 游戏搬砖教程

来喽来喽&#xff0c;最后纪元&#xff0c;一款《最后纪元》是一款以获得战利品为基础的暗黑风格动作RPG游戏&#xff0c;玩家将从2281年的毁灭时代追溯到由女神Eterra创造的世界&#xff0c;通过多个时代与黑暗的命运对抗&#xff0c;找到拯救世界的方式。游戏有五种职业&…

二叉平衡树(左单旋,右单旋,左右双旋、右左双旋)

一、AVL树&#xff08;二叉平衡树&#xff1a;高度平衡的二叉搜索树&#xff09; 0、二叉平衡树 左右子树高度差不超过1的二叉搜索树。 public class AVLTree{static class AVLTreeNode {public TreeNode left null; // 节点的左孩子public TreeNode right null; // 节点的…

【Unity2D 2022:NPC】制作NPC

一、创建NPC角色 1. 创建JambiNPC并同时创建Jambi站立动画 &#xff08;1&#xff09;点击第一张图片&#xff0c;按住shift不松&#xff0c;再选中后两张图片&#xff0c;拖到层级面板中 &#xff08;2&#xff09;将动画资源文件保存到Animation Clips文件夹中 &#xff08;…

三维引擎实践 - OSG渲染线程创建过程(未完待续)

一&#xff1a;概述 一个3D应用程序&#xff0c;在创建好图形窗口之后&#xff0c;就要使用该窗口的OpenGL上下文进行渲染相关工作了&#xff0c;本节分析下OSG源码中渲染线程的建立过程。 二&#xff1a;OSG渲染线程用到了哪些类&#xff1f; 1. GraphicsThread 类&#xff0c…

政安晨:【Keras机器学习示例演绎】(五十二)—— 使用门控残差和变量选择网络进行分类

目录 简介 数据集 安装准备 数据准备 定义数据集元数据 创建用于训练和评估的 tf.data.Dataset 创建模型输入 对输入特征进行编码 实施门控线性单元 实施门控余留网络 实施变量选择网络 创建门控残差和变量选择网络模型 编译、训练和评估模型 政安晨的个人主页&am…

怎么判断自己是否适合学习PMP?

判断自己是否适合学习PMP项目管理专业人士认证&#xff0c;可以从以下几个方面进行考量&#xff1a; 1、职业发展需求&#xff1a; 如果您在项目管理领域工作&#xff0c;或计划未来从事相关工作&#xff0c;PMP认证能显著提升您的竞争力。 对于项目经理、产品经理、技术领导…

什么是边缘计算?创造一个更快、更智慧、更互联的世界

前言 如今&#xff0c;数十亿物联网传感器广泛部署在零售商店、城市街道、仓库和医院等各种场所&#xff0c;正在生成大量数据。从这些数据中更快地获得洞察&#xff0c;意味着可以改善服务、简化运营&#xff0c;甚至挽救生命。但要做到这一点&#xff0c;企业需要实时做出决策…

【ESP32】打造全网最强esp-idf基础教程——16.SmartConfig一键配网

SmartConfig一键配网 一、SmartConfig知识扫盲 在讲STA课程的时候&#xff0c;我们用的是代码里面固定的SSID和密码去连接热点&#xff0c;但实际应用中不可能这么弄&#xff0c;我们得有办法把家里的WiFi SSID和密码输入到设备里面去&#xff0c;对于带屏带输入设备还…

15.x86游戏实战-汇编指令jmp call ret

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 工具下载&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1rEEJnt85npn7N38Ai0_F2Q?pwd6tw3 提…