[力扣_21] 合并两个有序链表

题目入口:点击进入

相关算法:

  • 归并排序

    • 递归——时间复杂度O(m+n),空间复杂度O(m+n)只有递归系统栈和若干指针
    • 迭代——时间复杂度O(m+n),空间复杂度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>

动图如下所示:

640.gif

代码如下所示:

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);
}

本文链接:

https://nullcode.fun/67.html
1 + 7 =
快来做第一个评论的人吧~