题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
分析
定义result储存结果,将两个链表各自遍历一遍,每次各拿出一个结点比较,把较小的连接在result后面,直到至少有一个链表元素全用完,此时,将另一个链表剩余部分直接连接在当前结果后面。
图解
代码
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* result = new ListNode(-1);
ListNode* cur1 = l1;
ListNode* cur2 = l2;
ListNode* cur = result;
while (cur1 != nullptr && cur2 != nullptr) {
if (cur1->val < cur2->val) {
cur->next = cur1;
cur1 = cur1->next;
}
else {
cur->next = cur2;
cur2 = cur2->next;
}
cur = cur->next;
}
if (cur1 == nullptr) cur->next = cur2;
if (cur2 == nullptr) cur->next = cur1;
return result->next;
}
};