Crack the Backend

Problem Statement

Merge two sorted linked lists list1 and list2 into one sorted linked list. Return the head of the merged list. The merged list should be built by splicing together the nodes of the first two lists. Either list may be null.

We compare the current heads of the two lists and take the smaller node, then advance that list. A dummy node simplifies handling the empty case and building the result.

Key Observations

Use a dummy node as the head of the result; maintain a tail pointer. While both list1 and list2 are non-null: if list1.val <= list2.val, attach list1 to tail, advance list1; else attach list2, advance list2. Then attach whichever list is still non-null to tail. Return dummy.next.
We do not create new nodes; we only change next pointers. O(1) space (excluding the result list).

Approach

High-level: 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. Then tail.next = list1 != null ? list1 : list2. Return dummy.next.

Steps:

ListNode dummy = new ListNode(0), tail = dummy. While both lists non-null: attach the smaller head to tail, advance that list and tail.
tail.next = (list1 != null) ? list1 : list2. Return dummy.next.

Implementation

Java

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;
}

Test Cases

Example 1

Input

list1 = [1,2,4], list2 = [1,3,4]

Expected

[1,1,2,3,4,4]

Explanation

Merged sorted.

Complexity Analysis

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

Follow-ups

Merge k sorted lists (heap or divide and conquer).