[力扣_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);
}

本文链接：