16. 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. Create a dummy node as the starting point of the merged list. This simplifies edge cases. A tail pointer tracks where to append next.

• dummy = ListNode()
  tail = dummy

2. While both lists have nodes, compare current nodes and attach the smaller one to the merged list.

• 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

3. When one list is exhausted, attach the remainder of the other list (already sorted).

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

4. Return dummy.next since dummy is a placeholder and the actual merged list starts after it.

• return dummy.next

Summary:

Use a dummy node and 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. The dummy node eliminates special head-handling logic.

Time and Space Complexity:

Time Complexity: O(n + m) - where n and m are the lengths of the two lists.

Space Complexity: O(1) - we only rearrange existing nodes.

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
    tail.next = list1 or 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;
    }
}