leetcode-21. 合并两个有序链表

本文最后更新于：2022年7月30日 晚上

  • 迭代和递归写法
  • 面试时会考虑去重，迭代去重在比较前判断pre和l1和l2的大小，决定是否要跳过该节点
  • 变形：合并多个有序列表：合并多个有序链表的实现思路，分析时间复杂度和空间复杂度。方法：以合并两个链表的思路为基础，使用归并自底向上合并。还有小顶堆，也就是优先队列。

迭代

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
33
34
35
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        ListNode* dummy = new ListNode(-1000); // 虚拟节点，为了返回列表方便

        ListNode* pre = dummy; // 操作指针

        while (list1 != NULL && list2 != NULL)
        {
            // 如果需要去重的话，先比较pre->val 和 list1, list2的val
            // if (pre->val == list1->val) list1 = list1->next;
            // if (pre->val == list2->val) list2 = list2->next;

            if (list1->val <= list2->val) 
            {
                pre->next = list1;
                list1 = list1->next;
                pre = pre->next;
            }
            else 
            {
                pre->next = list2;
                list2 = list2->next;
                pre = pre->next;
            }
        }

        // 最终有一个链表没有遍历完，就接在pre的后面.
        if (list1 == NULL) pre->next = list2;
        else pre->next = list1;

        return dummy->next;
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 终止条件
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;

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

    }
};