LeetCode //C - 21. Merge Two Sorted Lists

21. Merge Two Sorted Lists

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

Merge the two lists into 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.
?

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

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.

From: LeetCode
Link: 21. Merge Two Sorted Lists

---

Solution:

Ideas：

• We start by creating a dummy node that will serve as a placeholder to the start of our new list.
• The tail pointer is used to keep track of the end of the merged list.
• We loop through both list1 and list2 until we reach the end of one of them.
• In each iteration, we compare the values of the current nodes and append the smaller one to the merged list, moving the tail and the appropriate list pointer (list1 or list2) forward.
• If one of the lists is exhausted before the other, we simply append the remainder of the non-exhausted list to the merged list.
• Finally, we return the next node after dummy as it points to the start of our merged list.

Code:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // Create a dummy node to act as the start of the merged list.
    struct ListNode dummy;
    // Use a tail node to keep track of the last node in the merged list.
    struct ListNode *tail = &dummy;
    // The dummy node initially points to NULL.
    dummy.next = NULL;

    while (list1 && list2) {
        if (list1->val < list2->val) {
            // If the current node in list1 is less, add it to the merged list.
            tail->next = list1;
            list1 = list1->next;
        } else {
            // If the current node in list2 is less or equal, add it to the merged list.
            tail->next = list2;
            list2 = list2->next;
        }
        // Move the tail pointer forward.
        tail = tail->next;
    }

    // If there are remaining nodes in either list, append them to the merged list.
    if (list1) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }

    // The merged list is after the dummy node.
    return dummy.next;
}