《手撕链表题系列-5》合并两个有序链表
链表 系列 两个 合并 有序
2023-09-27 14:22:51 时间
前言
本系列主要讲解链表的经典题
注:划重点!!必考~
合并两个有序链表
- 题目描述:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
- 示例:
- 提示:
- 两个链表的节点数目范围是
[0, 50]
-100 <= Node.val <= 100
l1
和l2
均按 非递减顺序 排列
- 解题思路:
如果是到原链表本身上进行合并,则需要考虑的地方会比较多(实现起来很难)
这里我们选择使用尾插法
两个链表进行结点比较,较小的则将该结点进行尾插到另一个新链表上,再比较下一个
比较完一个链表后,另一个链表存在元素未比较,将该链表整体尾插
注:这里我们可以选择双指针尾插,也可以选择带哨兵卫头结点尾插
- 参考代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
//为空链表情况
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
//创建哨兵卫头结点
struct ListNode*newhead=malloc(sizeof(struct ListNode));
newhead->next=NULL;
//遍历指针
struct ListNode*cur1=l1,*cur2=l2,*cur3=newhead;
while(cur1&&cur2)
{
if(cur1->val>cur2->val)
{
cur3->next=cur2;
cur3=cur3->next;
cur2=cur2->next;
}
else
{
cur3->next=cur1;
cur3=cur3->next;
cur1=cur1->next;
}
}
//存留节点尾插
if(cur1)
{
cur3->next=cur1;
}
if(cur2)
{
cur3->next=cur2;
}
//记录哨兵后一个空间,并释放哨兵
struct ListNode*next=newhead->next;
free(newhead);
return next;
}
- 结果:
每日k题无烦恼,点赞学习不得了~
相关文章
- 数据结构系列学习(四) - 单向循环链表(Circular Linked List)
- C语言双链表,循环链表,静态链表讲解(王道版)
- 《手撕链表题系列-8》相交链表
- 《手撕链表题系列-3》找到链表的中间结点
- C++学习笔记_13 双向链表和链表模板 2021-05-06
- leetcode86. 分隔链表
- LeetCode·1669.合并两个链表·双指针
- LeetCode·92.反转链表||·头插法
- 114.二叉树展开为链表
- NLP自然语言处理系列-算法基础-买卖股票的最佳时机 反转链表 II 二叉树的右视图 爬楼梯
- [LeetCode] 206. Reverse Linked List 反向链表
- 链表求和(C语言)
- 找出链表中间结点的三种解法