Merge Two Sorted Lists

EasyLinked List Recursion

A help desk keeps two queues of open tickets. Each queue is a singly linked list sorted by priority score, from the most urgent ticket (lowest score) to the least urgent; escalated tickets have negative scores. At shift change the two queues must become one queue that is still sorted.

Given the heads list1 and list2, splice the existing nodes together into a single list in non-decreasing order and return its head. Reuse the nodes you are given instead of creating new ones. Either queue may be empty.

Example 1

Input: list1 = [-3,2,9], list2 = [0,2,5,11]
Output: [-3,0,2,2,5,9,11]

Explanation: Both tickets with score 2 stay in the merged queue.

Example 2

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

Explanation: When one queue is empty, the other queue is already the answer.

Example 3

Input: list1 = [10,20,30], list2 = [1,2]
Output: [1,2,10,20,30]

Explanation: Every ticket in list2 is more urgent, so both of them come first.

Constraints

Each queue holds between 0 and 100 tickets.
Priority scores are integers from -200 to 200.
Both lists are already 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