10. 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.

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

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

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

Problem Breakdown:

1. We create a dummy node to serve as the starting point of our merged list. This simplifies edge cases because we do not need to handle the head of the merged list separately. We also create a tail pointer to track where to append the next node.

• dummy = ListNode()
  tail = dummy

2. We iterate while both lists have nodes remaining. At each step, we compare the current nodes of both lists and append the smaller one to our merged list.

• while list1 and list2:

3. If list1's current value is smaller or equal, we attach list1's node to the tail of our merged list and advance list1 to its next node.

• if list1.val <= list2.val:
      tail.next = list1
      list1 = list1.next

4. Otherwise, list2's current value is smaller, so we attach list2's node and advance list2.

• else:
      tail.next = list2
      list2 = list2.next

5. After each attachment, we advance the tail pointer to the newly added node.

• tail = tail.next

6. When one list is exhausted, the other list may still have remaining nodes. Since they are already sorted, we simply attach the rest of the non-empty list to the tail.

• if list1:
      tail.next = list1
  elif list2:
      tail.next = list2

7. We return dummy.next because dummy is a placeholder and the actual merged list starts at the node after dummy.

• return dummy.next

Summary:

Use a dummy node and a tail pointer to build the merged list. Compare nodes from both lists, always picking the smaller value. When one list runs out, attach the remainder of the other list. The dummy node pattern eliminates special handling for the head of the result.

Time and Space Complexity:

Time Complexity: O(n + m) - where n and m are the lengths of the two lists, we visit each node once.

Space Complexity: O(1) - we only rearrange existing nodes without creating new ones (excluding the dummy node).

Python Solution:

def mergeTwoLists(list1, list2):
    dummy = ListNode()
    tail = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    if list1:
        tail.next = list1
    elif list2:
        tail.next = list2
    return dummy.next

JavaScript Solution:

var mergeTwoLists = function(list1, list2) {
    const dummy = new ListNode();
    let tail = dummy;
    while (list1 && list2) {
        if (list1.val <= list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }
    tail.next = list1 || list2;
    return dummy.next;
};

Java Solution:

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}