LeetCode 21 Merge Two Sorted Lists
题目分析
https://leetcode.com/problems/merge-two-sorted-lists/
很简单的题目。
直接法
时间复杂度 O(n)。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* head = new ListNode;
ListNode* c = head;
while (list1 != nullptr || list2 != nullptr) {
if (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
c->next = list1;
list1 = list1->next;
} else {
c->next = list2;
list2 = list2->next;
}
} else {
if (list1 == nullptr) {
c->next = list2;
list2 = list2->next;
} else {
c->next = list1;
list1 = list1->next;
}
}
c = c->next;
}
return head->next;
}
};
直接法（当其中一个为 nullptr 后直接接上的优化）
实际上其中一个为 nullptr 后我们可以直接拼接。
我 19 年的解法怎么比我 22 年的解法还要好，淦。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode result(0);
ListNode* last = &result;
while(l1 && l2){
if(l1->val<l2->val){
last->next = l1;
l1 = l1->next;
}else{
last->next = l2;
l2 = l2->next;
}
last = last->next;
}
last->next = l1 ? l1 : l2;
return result.next;
}
};