美文网首页
链表--合并两个有序链表 Leetcode 21

链表--合并两个有序链表 Leetcode 21

作者: Pig_deng饲养员 | 来源:发表于2020-09-02 10:14 被阅读0次

题目

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

思路

迭代法

因为两个链表是有序的,因此只要按顺序比较两个链表结点即可,小的结点加入到新的链表中,直到两个链表其中一个为空,然后将不为空的链表接到新链表末尾即可。
时间复杂度O(m+n),因为需要将两个链表遍历一遍
空间复杂度O(1),无需额外的内存

c++代码
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head=new ListNode(-1), *cur;

        cur = head;
        while(l1 != nullptr && l2 != nullptr){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }

        if(l1 == nullptr) cur->next = l2;
        else cur->next = l1;

        return head->next;
    }
};

递归法

采用递归的方法进行归并,假定现在两个链表当前结点都不为空, 那么归并的公式为

  1. l1的当前结点的值小于l2当前结点的值,那么归并结果为l1->next = merge(l1->next, l2),即让l1后面的链表和l2链表进行归并,返回l1当前结点。
  2. l1的当前结点的值大于等于l2当前结点的值,那么归并结果为l2->next = merge(l1, l2->next),即让l1链表和l2后面的链表进行归并,返回l2当前结点。

当两个链表其中一个为空时,返回另一个链表即可。
时间复杂度O(m+n)
空间复杂度O(m+n),因为有递归调用栈

c++代码
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }else if(l2 == nullptr){
            return l1;
        }

        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }

相关文章

网友评论

      本文标题:链表--合并两个有序链表 Leetcode 21

      本文链接:https://www.haomeiwen.com/subject/pdrvsktx.html