LeetCode 21.合并两个有序链表
2023-09-14 09:13:12 时间
难度: e a s y \color{Green}{easy} easy
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 ] [0, 50] [0,50]
- − 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100
- l 1 l1 l1 和 l 2 l2 l2 均按 非递减顺序 排列
算法
(线性合并) O(n)
- 建立头结点的保护结点
dummy
,设置cur
指针指向dummy
。 - 若当前
l1
指针指向的结点的值val
比l2
指针指向的结点的值val
小,则令cur
的next
指针指向l1
,且l1
后移;否则指向l2
,且l2
后移。 - 然后
cur
指针按照上一部设置好的位置后移。 - 循环以上步骤直到
l1
或l2
为空。 - 将剩余的
l1
或l2
接到cur
指针后边。
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
cur -> next = l1;
l1 = l1 -> next;
}else {
cur ->next = l2;
l2 = l2 ->next;
}
cur = cur -> next;
}
if (l1) cur -> next = l1;
if (l2) cur -> next = l2;
return dummy -> next;
}
};
相关文章
- Java实现 LeetCode 817 链表组件(暴力)
- Java实现 LeetCode 811 子域名访问计数 (暴力)
- Java实现 LeetCode 796 旋转字符串 (水题)
- Java实现 LeetCode 671 二叉树中第二小的节点(遍历树)
- Java实现 LeetCode 203 移除链表元素
- Java实现 LeetCode 148 排序链表
- Java实现 LeetCode 138 复制带随机指针的链表
- Java实现 LeetCode 21 合并两个有序链表
- LeetCode(92):反转链表 II
- LeetCode(21):合并两个有序链表
- 【数组&双指针】leetcode 234. 回文链表【简单】
- LeetCode-707. 设计链表【单链表,双链表】
- LeetCode-67. 二进制求和【位运算,字符串,数学,模拟】
- LeetCode-895. 最大频率栈【栈,哈希表,设计,有序集合】
- LeetCode-21. 合并两个有序链表
- (链表专题) 21. 合并两个有序链表 ——【Leetcode每日一题】
- 【LeetCode Python实现】119. 杨辉三角 II(中等)
- Leetcode 237. 删除链表中的节点
- [LeetCode] 148. 排序链表 ☆☆☆(归并排序)
- leetcode 88. 合并两个有序数组 js实现
- leetcode 13. Roman to Integer
- 【Leetcode刷题Python】92.反转链表II
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- LeetCode 430. 扁平化多级双向链表
- LeetCode 67. 二进制求和
- LeetCode 203. 移除链表元素
- 【LeetCode】21. 合并两个有序链表
- 【LeetCode】剑指 Offer II 024. 反转链表
- 【LeetCode】876.链表的中间节点