LeetCode 21 Merge Two Sorted Lists

Tag: 链表问题 LeetCode Posted on 2022-02-05 14:52:33 Edited on 2022-02-05 16:52:11 Views: 162

题目分析

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/