当前位置:网站首页>leetcode21. Merge two ordered linked lists
leetcode21. Merge two ordered linked lists
2022-08-11 05:46:00 【FussyCat】
leecode题链接:LeetCode21.合并两个有序链表
题目描述:
将两个升序链表合并为一个新的 升序 链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的.
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
解题思路:
分别使用递归法和迭代法.
以下用C语言实现:
递归法:
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if (l1 == NULL) {
return l2;
} else if (l2 == NULL) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
迭代法:
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode)); /* The chain of distribution header */
struct ListNode *prev = head;
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
prev->next = (l1 == NULL) ? l2 : l1; /* The situation of the first list is empty */
return head->next;
}
边栏推荐
猜你喜欢
随机推荐
基于TF-IDF 文本相似性实战 详细教程
C语言——文件操作(2)文件的读写操作
Minecraft
【C语言从初阶到进阶】第二篇 初始C语言(二)
吃瓜教程task04 第5章 神经网络
C语言自定义数据类型——联合体
gradle-wrapper.jar说明
我的四核Cortex-A53学习之路
【win10+cuda7.5+cudnn6.0安装caffe④】安装pycaffe
吃瓜教程task01 第2章 模型评估与选择
tensorflow代码翻译成pytorch代码 -详细教程+案例
(3) How Redis performs stress testing
Flask framework to study: the debug and configuration items
【动态代理】CGLIB 动态代理的使用及原理
怎么用管理员方式打开压缩包
2021研究生数学建模D题,BP神经网络和卷积神经网络解题代码(基于pytorch)
selenuim使用cookie登录京东
Chapter 13 Class Inheritance-1
吃瓜教程task02 第3章 线性模型
信息学奥赛