21

21. Merge Two Sorted Lists (Easy)

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

 

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

 

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

Related Topics:
Linked List, Recursion

Companies:
Amazon, Microsoft, Facebook, Google, Adobe, Apple, Bloomberg, Yahoo, Arista Networks, Uber, Indeed, Cisco, Tencent, Airbnb, Oracle, IBM, Huawei, Paypal, Yandex

Similar Questions:

• Merge k Sorted Lists (Hard)
• Merge Sorted Array (Easy)
• Sort List (Medium)
• Shortest Word Distance II (Medium)
• Add Two Polynomials Represented as Linked Lists (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/merge-two-sorted-lists/
// Author: github.com/lzl124631x
// Time: O(A + B)
// Space: O(1)
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        ListNode head, *tail = &head;
        while (a && b) {
            if (a->val <= b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return head.next;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/merge-two-sorted-lists/
// Author: github.com/lzl124631x
// Time: O(A + B)
// Space: O(1)
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        ListNode head, *p = &head;
        head.next = a;
        while (p->next && b) {
            if (p->next->val > b->val) {
                auto node = b;
                b = b->next;
                node->next = p->next;
                p->next = node;
            }
            p = p->next;
        }
        if (b) p->next = b;
        return head.next;
    }
};