题目描述

链表的合并

样例

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(nullptr) {}
};
ListNode* ListMerging(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* current = &dummy;
    while (l1!=nullptr&&l2!=nullptr)
    {
        if (l1->val < l2->val) {
            current->next = l1;
            l1 = l1->next;
        }
        else
        {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }
    if (l1 != nullptr) {
        current->next = l1;
    }
    else {
        current->next = l2;
    }
    return dummy.next;
}
void PrintNewList(ListNode* head) {
    while (head!=nullptr)
    {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}
void FreeMergedList(ListNode* head) {
    while (head!=nullptr)
    {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }

}
ListNode* InputList() {
    int n;
    cin >> n;
    if (n <= 0) return nullptr;
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        ListNode* l = new ListNode(val);
        if (head == nullptr) {
            head = l;
            tail = head;
        }
        else
        {
            tail->next = l;
            tail = l;
        }
    }
    return head;
}
int main() {
    ListNode* l1 = InputList();

    ListNode* l2 = InputList();

    ListNode* mergedList = ListMerging(l1, l2);
    PrintNewList(mergedList);
    FreeMergedList(mergedList);
    return 0;
}

----------

### 
#####



#### 时间复杂度

#### 参考文献


#### C++ 代码

```