24. Merge Two Sorted Lists

You are given the heads of two singly linked lists, list1 and list2, each sorted in non-decreasing order.

Combine them into one sorted list built by relinking the existing nodes (no need to allocate new ones), and return its head.

Example 1

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

Example 2

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

Example 3

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

Explanation: When one list is empty, the answer is simply the other list.

Constraints

Each list has between 0 and 100 nodes
-200 <= Node.val <= 200
Both lists are sorted in non-decreasing order

💡 Hint 1

At every step the next node of the result is the smaller of the two current heads.

💡 Hint 2

A dummy (sentinel) node in front of the result saves you from special-casing the first node.

💡 Hint 3

Once one list runs out, attach the rest of the other list in one step.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Create a dummy node and a tail pointer that always points at the last node of the merged list. While both lists still have nodes, compare their heads, hang the smaller one off tail, and advance that list. When one list is exhausted, the other is already sorted, so link its remainder to tail in one step. The merged list starts at dummy.next. Taking from list1 on ties keeps the merge stable.

Time O(n + m)Space O(1)

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(0);
  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;
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0), 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;
    }
}

/**
 * Definition for singly-linked list (provided):
 * function ListNode(val, next) { this.val = val ?? 0; this.next = next ?? null; }
 *
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
function mergeTwoLists(list1, list2) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit