前言
本系列主要讲解链表的经典题 注:划重点!!必考~
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
[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题无烦恼,点赞学习不得了~