[力扣_21] 合并两个有序链表
题目入口:点击进入
相关算法:
- 归并排序
- 递归——时间复杂度O(m+n),空间复杂度O(m+n)只有递归系统栈和若干指针
- 迭代——时间复杂度O(m+n),空间复杂度O(1)只有若干指针类型变量
思路和算法:
对于这种两个升序线性表需要合并成一个线性表的题,我们在线性表的数据结构题解里并不陌生,由于两链表是排序好的,所以第i的位置必定比i+1的位置小,我们只需要依次比较两链表内的元素,对小的进行连接,直到一表为空或两表为空即可
迭代
我们可用一个指针定义一个虚结点(假设为dim),再使用两个指针(假设为l1,l2)分别指向两链表的头,一个指针指向虚结点(假设为head)。
如下图示:
代码如下所示:
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(!l1) return l2;
if(!l2) return l1;
if(!l1&&!l2) return NULL;
struct ListNode *head,*p;
if(l1->val < l2->val){
head=l1;
l1=l1->next;
}
else
{
head=l2;
l2=l2->next;
}
p=head;
while(l1&&l2)
{
if(l1->val < l2->val)
{
p->next=l1;
l1=l1->next;
}
else{
p->next=l2;
l2=l2->next;
}
p=p->next;
}
if(l1)
p->next=l1;
else
p->next=l2;
return head;
}
递归
根据以上规律考虑本题目:
终止条件:当两个链表都为空时,表示我们对链表已合并完成。 如何递归:我们判断 l1 和 l2 头结点哪个更小,然后较小结点的 next 指针指向其余结点的合并结果。(调用递归)
图示如下:
动图如下所示:
代码如下所示:
struct ListNode* digui(struct ListNode *l1,struct ListNode *l2)
{
if(!l1) return l2;
if(!l2) return l1;
if(l1->val<l2->val){ l1->next=digui(l1->next,l2);
return l1;
}
else{ l2->next=digui(l1,l2->next);
return l2;
}
}
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
return digui(l1,l2);
}