LeetCode21合并两个有序链表

Posted on | | Visitors:
Words count in article: 566 字 | Reading time ≈ 2 分

[toc]

题目介绍

题解一

解题思路

  • 递归法

    取出当前2个链表中头结点较小的那个链表的头结点，然后通过递归将2个链表合并（a->next和b）。

  • 复杂度分析

    假设3个链表分别有n和m个结点，则时间复杂度为$O(n+m)$、空间复杂度为$O(n+m)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 边界和递归出口
        if(nullptr==l1){return l2;}
        if(nullptr==l2){return l1;}
        // 递归表达式
        if(l1->val<l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};

题解二

解题思路

  • 迭代法

    用pre保存前1个结点，用2个指针分别遍历这2个链表每次取出值最小的结点，然后拼接成新的链表。当其中1个链表遍历结束，将另外1个链表直接拼接在新的链表的尾部。

  • 复杂度分析

    假设2个链表的长度分别是n和m，则最大时间复杂度为$O(n+m)$、空间复杂度为$O(1)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 定义头结点，方便建立新链表
        ListNode *head = new ListNode(-1);
        // 遍历链表用的指针
        ListNode *l3 = head;
        // 同时遍历两个链表并拼接值较小的结点到新链表中，同步更新链表指针，直至某个链表遍历结束
        while (l1 != nullptr && l2 != nullptr){
            if (l1->val < l2->val){
                l3->next = l1;
                l1 = l1->next;
            }else{
                l3->next = l2;
                l2 = l2->next;
            }
            l3 = l3->next;
        }
        // 将未遍历完的链表拼接至新链表
        if(l1!=nullptr){
            l3->next = l1;
        }
        if (l2 != nullptr){
            l3->next = l2;
        }

        // 释放无意义头结点并返回其next
        l3 = head->next;
        delete head;
        return l3;
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!