leetcode21：合并两个有序链表

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
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) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    递归实现
    
    时间复杂度：O(m+n)
        其中 m 和 n 分别是两个链表的长度，遍历两个链表各一次。
    空间复杂度：O(m+n)
        递归调用函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。
        结束递归调用时，函数最多调用 m+n，空间复杂度为 O(m+n)。
*/
class Solution_0 {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *p1 = list1, *p2 = list2;
        if (p1 == nullptr) {
            return p2;
        }
        if (p2 == nullptr) {
            return p1;
        }

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

/*
    迭代实现

    虚拟头结点 dummy 相当于占位符，避免处理空指针的情况。
    l1, l2 类似于拉链两侧的锯齿，指针 p 是拉链的拉索，将两个有序链表合并。

    时间复杂度：O(n)
        其中 m 和 n 分别为两个链表的长度，遍历两个链表各一次。
    空间复杂度：O(1)
*/
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummy = new ListNode(-1), *p = dummy;
        ListNode *p1 = list1, *p2 = list2;

        while (p1 && p2) {
            if (p1->val < p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = (p1 ? p1 : p2);
        
        return dummy->next;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> l1_cases = {
        {1,2,4},
        {},
        {},
    };
    vector<vector<int>> l2_cases = {
        {1,3,4},
        {},
        {0},
    };

    for (int i = 0; i < l1_cases.size(); i++) {
        ListNode* l1 = createList(l1_cases[i]);
        ListNode* l2 = createList(l2_cases[i]);

        cout << "Input List1: ";
        printList(l1);
        cout << "Input List2: ";
        printList(l2);

        ListNode* merged = solution.mergeTwoLists(l1, l2);
        cout << "Merged List: ";
        printList(merged);
    }

    return 0;
}