Ieetcode——21.合并两个有序链表

devtools/2024/9/23 11:20:20/

21. 合并两个有序链表 - 力扣(LeetCode)

合并两个有序链表我们的思路是创建一个新链表,然后遍历已知的两个有序链表,并比较其节点的val值,将小的尾插到新链表中,然后继续遍历,直到将该两个链表的全部节点全部尾插到新链表中。下面我来画图分析一下如何进行遍历和尾插:

遍历和尾插的过程就如上图一般,接下来我们来实现代码。

我们在写代码的时候还应该注意一些特殊情况:有序链表为空的情况。 

我们看,对于这两种情况下:如果两个有序链表都为空,那么就返回NULL;如果只有一个为空,那就返回另外一个。 

分析到这里,我们就可以开始写代码了。(注意:该代码只包含解决该问题的函数部分,不包含主函数内容)

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{//有空链表if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//无空链表//创建新链表,遍历两链表ListNode* newlist = NULL;ListNode* newtail = NULL;while(list1 && list2)//这两个链表只要有一个走到了NULL,就说明为NULL的链表已经全部尾插完了{if(list1->val <= list2->val){if(newlist == NULL){//新链表为空newlist = list1;newtail = list2;}else{//新链表不为空newtail->next = list1;newtail = newtail->next;}//尾插完后,遍历下一个节点list1 = list1->next;}else{if(newlist == NULL){//新链表为空newlist = list1;newtail = list2;}else{//新链表不为空newtail->next = list1;newtail = newtail->next;}//尾插完后遍历下一个节点list2 = list2->next;}}//跳出循环,说明有一个链表已经遍历完了,只需将另一个链表的剩余元素尾插到新链表if(list1 == NULL){//list1遍历完了,将list2尾插到新链表中newtail->next = list2;}else{//list2遍历完了,将list1尾插到新链表中newtail->next = list1;}return newlist;
}

我们写完之后,代码虽然可以成功解决问题,但是其中出现了很多重复的代码。 

哨兵位是一个有空间但是没有值的节点,而且是动态开辟的内存空间,所以我们现在就不能直接返回newist了,而是返回newlist->next,但是动态开辟的内存空间我们使用完之后就应该释放掉,所以我们应该先创建一个临时变量将newist->next存起来,然后将newlist释放掉,后返回临时变量。

所以我们要对该代码进行两部分的调整:

部分一:用来解决重复代码

部分二:用来解决动态内存开辟的释放以及哨兵位的引入对返回值的影响 

下面附上完整代码:

typedef struct ListNode ListNode;//避免因为类型名长而对其进行重命名
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{//有空链表if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//无空链表//创建新链表,遍历两链表ListNode* newlist = (ListNode*)malloc(sizeof(ListNode));ListNode* newtail = newlist;while(list1 && list2)//这两个链表只要有一个走到了NULL,就说明为NULL的链表已经全部尾插完了{if(list1->val <= list2->val){newtail->next = list1;newtail = newtail->next;//尾插完后,遍历下一个节点list1 = list1->next;}else{newtail ->next = list2;newtail = newtail->next;//尾插完后遍历下一个节点list2 = list2->next;}}//跳出循环,说明有一个链表已经遍历完了,只需将另一个链表的剩余元素尾插到新链表if(list1 == NULL){//list1遍历完了,将list2尾插到新链表中newtail->next = list2;}else{//list2遍历完了,将list1尾插到新链表中newtail->next = list1;}ListNode* ret = newlist->next;free(newlist);newlist = NULL;return ret;
}

 完!


http://www.ppmy.cn/devtools/30775.html

相关文章

Docker-Compose编排LNMP并部署WordPress

前言 随着云计算和容器化技术的快速发展&#xff0c;使用 Docker Compose 编排 LNMP 环境已经成为快速部署 Web 应用程序的一种流行方式。LNMP 环境由 Linux、Nginx、MySQL 和 PHP 组成&#xff0c;为运行 Web 应用提供了稳定的基础。本文将介绍如何通过 Docker Compose 编排 …

Linux|awk 特殊模式“BEGIN 和 END”

引言 在本文[1]&#xff0c;我们将介绍Awk的更多特性&#xff0c;特别是两个特殊的模式&#xff1a;BEGIN和END。 这些独特的功能在我们努力扩展和深入探索构建复杂Awk操作的多种方法时&#xff0c;将大有裨益。 实例 让我们从Awk系列的开篇回顾开始&#xff0c;回想一下&#…

【研发日记】Matlab/Simulink避坑指南(十一)——Delay周期Bug

文章目录 前言 背景介绍 问题描述 分析排查 解决方案 总结归纳 前言 见《研发日记&#xff0c;Matlab/Simulink避坑指南(六)——字节分割Bug》 见《研发日记&#xff0c;Matlab/Simulink避坑指南(七)——数据溢出钳位Bug》 见《研发日记&#xff0c;Matlab/Simulink避坑指…

25计算机考研院校数据分析 | 哈尔滨工业大学

哈尔滨工业大学&#xff08;Harbin Institute of Technology&#xff09;&#xff0c;简称哈工大&#xff0c; 校本部位于黑龙江省哈尔滨市&#xff0c;是由工业和信息化部直属的全国重点大学&#xff0c;位列国家“双一流”、“985工程”、“211工程”&#xff0c;九校联盟 、…

windows ubuntu sed,awk,grep篇,8,Awk 语法和基础命令

目录 51.Awk 命令语法 52.Awk 程序结构(BEGIN,body,END)区域 53.打印命令 54.模式匹配 Awk 是一个维护和处理文本数据文件的强大语言。在文本数据有一定的格式&#xff0c;即每行数据包 含多个以分界符分隔的字段时&#xff0c;显得尤其有用。即便是输入文件没有一定的格式&a…

【Flask 系统教程 3】请求与响应

Flask 是一个灵活而强大的 Web 框架&#xff0c;而请求与响应则是构建 Web 应用的核心组成部分。在本文中&#xff0c;我们将探讨 Flask 中请求与响应的各种用法&#xff0c;包括不同的请求方法、重定向、响应对象、获取查询参数以及文件上传等。 请求 在 Flask 中&#xff0…

ue引擎游戏开发笔记(26)——处理角色死亡敌人仍攻击bug

1.需求分析 对游戏中存在的各种小问题做细节处理&#xff0c;例如玩家在死亡后&#xff0c;敌人仍对着目标开炮&#xff0c;并且仍然触发爆炸效果。 2.操作实现 1.首先分析问题起因&#xff0c;是由于虽然玩家控制的小车被摧毁了&#xff0c;但控制器仍然存在&#xff0c;没有…

华为OD机试 - 会议室占用时间段(Java 2024 C卷 100分)

华为OD机试 2024C卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;A卷B卷C卷&#xff09;》。 刷的越多&#xff0c;抽中的概率越大&#xff0c;每一题都有详细的答题思路、详细的代码注释、样例测试…