官方答案
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
// 合并后 l1 和 l2 最多只有一個(gè)還未被合并完拂铡，我們直接將鏈表末尾指向未合并完的鏈表即可
prev->next = l1 == nullptr ? l2 : l1;
return preHead->next;
}
};
思路：
新建一個(gè)鏈表preHead，新建指針prev指向該表的表尾萨螺；
然后分別對l1和l2進(jìn)行比較和遍歷决乎，每次比較將較小的節(jié)點(diǎn)連接在新的鏈表上；然后該鏈表的指針向后移一位佃迄，并且prev向后移一位泼差；
直到l1或l2其中有一個(gè)鏈表被遍歷完，接將鏈表末尾指向未合并完的鏈表即可呵俏；
注意這里返回的是preHead的后一個(gè)指針堆缘，因?yàn)榈谝粋€(gè)指針為頭指針不存放數(shù)據(jù)（被初始化為-1）。
