Merge Two Sorted Lists

Problem

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Constraints

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

Solution

The problem Merge Two Sorted Lists can be substituted with the following.

Create an implementation of merging process in a merge sort.

As both lists are guarenteed to be sorted in a non-decreasing order, a merged list can be created by selecting nodes with smaller values from each lists until both lists reaches the end.

Implementation

/**
 * 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 *list1, ListNode *list2)
    {
        ListNode *head = new ListNode();
        ListNode *cur = head;

        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                cur = cur->next = list1;
                list1 = list1->next;
            }
            else
            {
                cur = cur->next = list2;
                list2 = list2->next;
            }
        }
        cur->next = list1 ? list1 : list2;

        return head->next;
    }
};