[LeetCode] 21. Merge Two Sorted Lists

Description

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Analyse

合并两个有序的链表l1，l2

最简单的做法是新建一个链表l3，从l1和l2中获取最小的元素，插入新链表，其中一个链表的元素用完后，将另一个链表全部插入l3

时间复杂度O(m+n) (m,n为l1，l2长度)

最大比较次数
m + n - 1
l3长度为m+n，每比较一次l3长度+1，最后一个元素不用比较

    1   3   5  7
    | / | / | /
    2   4   6

最小比较次数
min(m, n)

    1   3
    | /
    4   5   6

Code

写出第一个版本，这个版本耗时长，消耗的内存也大，原因是新链表l3中的每个节点都是新建的，这其实没必要，可以改为重复使用l1,l2中的节点

 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
 {
    ListNode* l3 = new ListNode(NULL);
    ListNode* cur = l3;
    while (l1 || l2)
    {
        ListNode *tmp = new ListNode(NULL);

        if (!l1) {cur->next = l2; break;}
        if (!l2) {cur->next = l1; break;}

        if (l1->val < l2->val)
        {
            tmp->val = l1->val;
            l1 = l1->next;
        }
        else
        {
            tmp->val = l2->val;
            l2 = l2->next;
        }

        cur->next = tmp;
        cur = cur->next;
    }

    return l3->next;
}

做一些修改，重复利用l1, l2中的节点，这样就能够faster than 99%了

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
    ListNode* result = new ListNode(0);
    ListNode* cur = result;
    while (l1 && l2)
    {
        if (l1->val < l2->val)
        {
            cur->next = l1;
            l1 = l1->next;
        }
        else
        {
            cur->next = l2;
            l2 = l2->next;
        }

        cur = cur->next;
    }

    if (l1)
    {
        cur->next = l1;
    }
    else
    {
        cur->next = l2;
    }

    return result->next;
}

l3的第一个节点被浪费了，可以进一步修改

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
    if (!l1 || !l2) { return l1 ? l1 : l2;}

    ListNode* result;
    if (l1->val < l2->val)
    {
        result = l1;
        l1 = l1->next;
    }
    else
    {
        result = l2;
        l2 = l2->next;
    }

    ListNode* cur = result;
    while (l1 && l2)
    {
        if (l1->val < l2->val)
        {
            cur->next = l1;
            l1 = l1->next;
        }
        else
        {
            cur->next = l2;
            l2 = l2->next;
        }

        cur = cur->next;
    }

    if (l1)
    {
        cur->next = l1;
    }
    else
    {
        cur->next = l2;
    }

    return result;
}

LeetCode上的最优解是用递归

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1 || !l2) return l1 ? l1 : l2;

    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
    l2->next = mergeTwoLists(l1, l2->next);
    return l2;
}