LeetCode|Merge Two Sorted Lists-蒲公英云

LeetCode|Merge Two Sorted Lists

你的名字 2022-09-25 03:24 139阅读 0赞

【问题描述】

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

【解答1】

特殊情况：若有一个链表为空，则返回另一个链表。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL || l2 == NULL)
            return l1 == NULL ? l2 : l1;
        ListNode* nln;
        ListNode* nl1 = l1;
        ListNode* nl2 = l2;
        if (l1 != NULL && l2 != NULL)
            if (l1->val >= l2->val) {
                nln = l2;
                nl2 = l2->next;
            } else {
                nln = l1;
                nl1 = l1->next;
            }
        else
            ;
        ListNode* rln = nln;
        while (nl1 != NULL && nl2 != NULL) {
            if (nl1->val >= nl2->val) {
                nln->next = nl2;
                nln = nln->next;
                nl2 = nl2->next;
            } else {
                nln->next = nl1;
                nln = nln->next;
                nl1 = nl1->next;
            }
        }
        while (nl2 != NULL) {
            nln->next = nl2;
            nln = nln->next;
            nl2 = nl2->next;
        }
        while (nl1 != NULL) {
            nln->next = nl1;
            nln = nln->next;
            nl1 = nl1->next;
        }
        return rln;
    }
};

看到这个运行时间太久啦，才击败了3.几%的人，哼，不可以，我要改进一下！

12ms

【解答2】

改进1：把头结点的赋值和其他结点放在一起，返回时返回其next即可。学习之。

改进2：将第一个while中，if-else语句中共同的一个语句，提取出来。

运行时间为8ms，击败了70几%的人，耶~不错哦~

主要时间性能提升在于改进2~为什么呢？这里还没有想明白~

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL || l2 == NULL)
            return l1 == NULL ? l2 : l1;
        ListNode* nln=new ListNode(0);
        ListNode* nl1 = l1;
        ListNode* nl2 = l2;
        ListNode* rln = nln;
        while (nl1 != NULL && nl2 != NULL) {
            if (nl1->val >= nl2->val) {
                nln->next = nl2;
                nl2 = nl2->next;
            } else {
                nln->next = nl1;
                nl1 = nl1->next;
            }
            nln = nln->next;
        }
        while (nl2 != NULL) {
            nln->next = nl2;
            nln = nln->next;
            nl2 = nl2->next;
        }
        while (nl1 != NULL) {
            nln->next= nl1;
            nln = nln->next;
            nl1 = nl1->next;
        }
        return rln->next;
    }
};