LeetCode

21. Merge Two Sorted Lists(Easy)

查阅更多的题解,请点击

Problem

21. Merge Two Sorted Lists(Easy)

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

Solution

O(m+n) time, O(1) space

题目本身是一道很简单的题目,一个简单的归并排序
GitHub传送门

class Solution
{
  public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;
        ListNode *root = nullptr;
        if (l1->val < l2->val)
        {
            root = l1;
            l1 = l1->next;
        }
        else
        {
            root = l2;
            l2 = l2->next;
        }
        ListNode *node = root;
        while (l1 != nullptr && l2 != nullptr)
        {
            if (l1->val < l2->val)
            {
                node->next = l1;
                l1 = l1->next;
                node = node->next;
            }
            else
            {
                node->next = l2;
                l2 = l2->next;
                node = node->next;
            }
        }
        if (l1 != nullptr)
            node->next = l1;
        else
            node->next = l2;
        return root;
    }
};

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注