Leetcode Study Day 28

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.

My solution

The solution is to use a dummy node to simplify the edge cases. Then we use a while loop to iterate through both linked lists. We compare the values of the current nodes of the two linked lists. We add the smaller one to the merged list. Then we move the current pointer of the merged list to the next node. We also move the current pointer of the linked list that we add the node from to the next node. We repeat this process until one of the linked lists is empty. Then we add the rest of the other linked list to the merged list. Then we return the actual head of the merged list.

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummyHead = new ListNode();  // Create a dummy node to simplify edge cases.
        ListNode* current = dummyHead;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        if (list1) {
            current->next = list1;
        } else {
            current->next = list2;
        }
        ListNode* mergedHead = dummyHead->next;  // The actual start of the merged list.
        delete dummyHead;  // Remove the dummy node.
        return mergedHead;
    }
};