剑指 Offer 25. 合并两个排序的链表
2023-09-14 09:13:11 时间
难度: e a s y \color{Green}{easy} easy
题目描述
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
限制:
0 < = 链表长度 < = 1000 0 <= 链表长度 <= 1000 0<=链表长度<=1000
注意:本题与主站 21 题相同:https://leetcode-cn.com/problems/merge-two-sorted-lists/
算法
(线性合并) 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(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(-1);
auto cur = dummy;
while (l1 && l2) {
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;
}
};
相关文章
- 选择排序 c语言(链表法)「建议收藏」
- 【RTOS训练营】课程学习方法和结构体知识复习 + 链表知识
- LeetCode 237. 删除链表中的节点
- 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
- C语言链表详解_c语言中链表的使用
- LintCode 链表排序[通俗易懂]
- 链表排序总结(全)(C++)[通俗易懂]
- C 单向链表排序_单向链表排序java
- js的链表排序_排序js
- 【数据结构】LinkedList与链表
- Redis数据结构之链表详解
- 链表-头结点和头指针的区别详解编程语言
- 算法-合并两个排序的链表详解编程语言
- 算法练习之x的平方根,爬楼梯,删除排序链表中的重复元素, 合并两个有序数组详解编程语言
- 构建双向链表:在Linux环境下的实现(双向链表linux)
- Oracle中高效使用链表查询技巧(oracle中链表查询)
- 利用Redis实现高效的链表结构(redis 链表结构体)