合并两个排序的列表

发表于 更新于 分类于 本文字数： 869 阅读时长 ≈ 3 分钟

JZ25合并两个排序的列表

描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤10000≤n≤1000，−1000≤节点值≤1000−1000≤节点值≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

img

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

img

示例1

1
2
输入：{1,3,5},{2,4,6}
返回值：{1,2,3,4,5,6}

示例2

1
2
输入：{},{}
返回值：{}

示例3

1
2
输入：{-1,2,4},{1,3,4}
返回值：{-1,1,2,3,4,4}

题解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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* List1 = pHead1;
        ListNode* List2 = pHead2;
        
        //二者其中一个为空时返回另一个。
        if (List1==NULL) {
            return List2;
        }else if (List2==NULL) {
            return List1;
        }
        
        //初始化新链表头为两个链表中第一个元素较小的那一个头
        ListNode* ans_head;
        if(List1->val <= List2->val){
            ans_head = List1;
            List1 = List1->next;
        }else{
            ans_head = List2;
            List2 = List2->next;
        }
        ListNode* ans = ans_head;
        
        //头插法，双指针同时遍历两个链表，选择两个链表中较小的那一个插入到新的链表里面去
        while (true) {
            
            //如果某个链表已经插完了，则把另一个链表插入到当前处，跳出
            if (List1==NULL) {
                ans_head->next = List2;
                break;
            }
            if (List2==NULL) {
                ans_head->next = List1;
                break;
            }
            
            //判断+头插
            if (List1->val <= List2->val) {
                ans_head->next = List1;
                List1 = List1->next;
            }else {
                ans_head->next = List2;
                List2 = List2->next;    
            }
            ans_head = ans_head->next;
        }
        return ans;
    }
};

该题解与官方C++题解方法1：双指针迭代思路相同

题解2

该题解来自官方C++题解方法2

在双指针访问的思路下扩展递归，当把两个链表中较小的那个节点取出后，把剩下的两个链表的合并问题当作新的合并问题继续处理，这样每次取出的都是两个链表中的最小值，直到某一个被取空，则直接将另一个拼接到最后。缺点是相对题解1（$O(1)$）需要更多空间复杂度（$O(n)$）

代码

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
36
37
38
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //一个已经为空了，返回另一个
        if(pHead1 == NULL) 
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        
        //先用较小的值的节点
        if(pHead1->val <= pHead2->val){ 
            //递归往下
            pHead1->next = Merge(pHead1->next, pHead2); 
            return pHead1; 
        }else{
            //递归往下
            pHead2->next = Merge(pHead1, pHead2->next); 
            return pHead2;
        }
    }
};