Merge Two Sorted Lists — Practice

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. Return the head of the merged linked list.

Examples

Example 1

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

Output: [1,1,2,3,4,4]

Constraints

•The number of nodes in both lists is in the range [0, 50].
•-100 <= Node.val <= 100

Hints

Hint 1

Use a dummy head node to simplify edge cases at the start of the list — it removes the need for a special first-node check.

Hint 2

A recursive alternative is often considered more elegant: whichever list's current head is smaller becomes the result's head, with its .next set to the recursive merge of the remainder — at the cost of O(m+n) recursion-stack space versus the iterative version's O(1).

Solutions

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
        else                  { curr.next = l2; l2 = l2.next; }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2; // attach remaining
    return dummy.next;
}

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