代码语言：javascript复制
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
/* *
* Definition for singly-linked list.
* 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) {}
* };
*/
// 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) {}
// };
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
if (list1) {
tail->next = list1;
}
if (list2) {
tail->next = list2;
}
ListNode* result = dummy->next;
delete dummy;
return result;
}
};这段代码是一个经典的链表合并算法，用于合并两个已排序的链表。下面是对这段代码的解释：
创建一个哑节点（dummy）作为合并后链表的头部，并创建一个指针 tail 指向 dummy，同时初始化为0。
代码语言：javascript复制ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;使用 while 循环遍历两个输入链表 list1 和 list2，进行合并操作，直到其中一个链表为空。
代码语言：javascript复制while (list1 && list2) {
// 选取较小的节点连接到合并链表的尾部
if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}在循环结束后，将剩余的非空链表直接连接到合并链表的尾部。
代码语言：javascript复制if (list1) {
tail->next = list1;
}
if (list2) {
tail->next = list2;
}最后，获取合并后链表的头部节点，删除哑节点，返回合并后的链表。
代码语言：javascript复制ListNode* result = dummy->next;
delete dummy;
return result;这段代码的时间复杂度为 O(n m)，其中 n 和 m 分别是输入链表 list1 和 list2 的长度，因为每个节点只会被访问一次。
