程序地带

算法:合并两个有序链表


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


示例:


输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4


class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
}
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};

递归就是一个压栈和弹栈的过程,每次对一个节点进行压栈,然后重新链表的末尾开始弹栈,直到一直弹栈赋值到新链表的首节点。


class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
prev->next = l1 == nullptr ? l2 : l1;
return preHead->next;
}
};

 


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ma2595162349/article/details/109757384

随机推荐

这可能是有关英特尔®性能库最全的介绍了!

直到今天,英特尔仍在努力完善优化库,以获得英特尔®处理器的最大性能。英特尔®性能库为开发人员提供了大量经过测试的预构建和性能优化的功能。通过利用这些库,开发人...

yuyuyuyo 阅读(986)

STL总结之<list容器>

标准模板库:list容器来,看黑板:链表是由一系列结点组成,每个结点包括两个部分:一个是存储数据元素的数据域,另一个...

All In !!! 阅读(510)

HX1188NL 普思Pulse 网络变压器

制造商编号:HX1188NL制造商:PulseElectronics说明:AudioTransformers/SignalTransformers100Bas...

林臻皓 阅读(673)

习题8-4 报数 (20分)

习题8-4报数(20分)报数游戏是这样的:有n个人围成一圈,按顺序从1到n编好号。从第一个人开始报数,报到m(<n)的人退出...

mistymountain32 阅读(295)

网络层

目录概述IP数据报格式分组转发算法IP地址编址方式分类子网划分子网掩码无分类(CIDR构造超网)地址解析协议ARP网际控制报文协议(ICMP)路...

清风拂腿 阅读(925)

2020-11-26

Java中Object类的方法Object是所有类的终极父类1.clone方法保护方法,实现对象的浅复制,只有实现了Cloneable接口才可以调用该方法&#...

旋 律 阅读(789)

k8s 安装jenkins

1、下载镜像,指定版本dockerpulljenkins/jenkins:2.267一般需要采用最新版本,同时不能用latest,latest带的版本也不是最...

xzhongb 阅读(535)

在git中出现中文乱码的解决方案

在gitbash中出现中文汉字乱码的情况274232350256256346200273347273223.png解决方案:在bash提示符下输入:gi...

zhangvalue 阅读(639)