合并两个有序链表

题意

合并两个升序链表，返回新链表。

思路

迭代：dummy 头结点简化边界处理，每次选取较小节点接入，最后将剩余链直接接上。

递归：每次选较小节点，递归合并剩余部分。

代码

cpp

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/**
 * Author by Rainboy
 */
// main.cpp：dummy 头结点，迭代接入较小节点，O(n+m)。
#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(0), *cur = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

ListNode *build(istream &in, int n) {
    if (!n)
        return nullptr;
    auto head = new ListNode(0), cur = head;
    for (int i = 0, v; i < n; i++) {
        in >> v;
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    return head->next;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    auto a = build(cin, n), b = build(cin, m);
    auto head = Solution().mergeTwoLists(a, b);
    for (auto p = head; p; p = p->next)
        cout << p->val << ' ';
    return 0;
}

python

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#!/usr/bin/env python3
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next


def build(arr):
    dummy = cur = ListNode(0)
    for v in arr:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next


def main() -> None:
    n, m = map(int, input().split())
    a = build(list(map(int, input().split())))
    b = build(list(map(int, input().split())))
    head = Solution().mergeTwoLists(a, b)
    while head:
        print(head.val, end=" ")
        head = head.next


if __name__ == "__main__":
    main()

复杂度

时间复杂度：O(n+m)。
空间复杂度：O(1) 迭代，O(n+m) 递归。

总结

dummy 头结点是链表操作中处理边缘条件（空链表、删头节点等）的标准技巧。

合并两个有序链表

目录

题意

思路

代码

复杂度

总结