[力扣_21] 合并两个有序链表
题目入口：点击进入
相关算法：
归并排序
- 递归——时间复杂度O（ｍ＋ｎ），空间复杂度Ｏ（ｍ＋ｎ）只有递归系统栈和若干指针
- 迭代——时间复杂度Ｏ（ｍ＋ｎ），空间复杂度Ｏ（1）只有若干指针类型变量
思路和算法：
对于这种两个升序线性表需要合并成一个线性表的题，我们在线性表的数据结构题解里并不陌生，由于两链表是排序好的，所以第i的位置必定比i+1的位置小，我们只需要依次比较两链表内的元素，对小的进行连接，直到一表为空或两表为空即可
迭代
我们可用一个指针定义一个虚结点（假设为dim），再使用两个指针（假设为l1,l2）分别指向两链表的头，一个指针指向虚结点(假设为head)。
如下图示：
<video controls="" src="https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/LeetCode~21.mp4";></video>
代码如下所示：
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 指针指向其余结点的合并结果。（调用递归）
图示如下：
<video controls="" src="https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/LeetCode21digui~1.mp4";></video>
动图如下所示：
代码如下所示：
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);
}