Merge Two Sorted Lists

Merge Two Sorted Lists

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.

Solutions

🧠 Cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        //input validation
        if(!l1 && !l2)
            return nullptr;
        if(!l1)
            return l2;
        if(!l2)
            return l1;

        //init of vars
        ListNode *&min_val_node = l1->val < l2->val ? l1 : l2;
        const int start_val = min_val_node->val;
        min_val_node = min_val_node->next;

        ListNode *new_list_start = new ListNode(start_val),
                 *new_list_iter = new_list_start;

        //O(n) solution, two pointers
        //while we have somthing in lists - merge them
        while(l1 || l2)
        {
            if(l2 == nullptr || (l1 && l1->val < l2->val)) 
            {
                new_list_iter->next = new ListNode(l1->val);
                new_list_iter = new_list_iter->next;
                l1 = l1->next;
            }
            else
            {
                new_list_iter->next = new ListNode(l2->val);
                new_list_iter = new_list_iter->next;
                l2 = l2->next;
            }
        }

        return new_list_start;
    }
};