LeetCode. 21. Merge Two Sorted Lists

Link

Approach

Use a dummy head to simplify building the result, and keep a tail pointer at the last node appended. While both input lists are non-null, append the smaller current node and advance only the list that supplied it. The result is always sorted, and contains exactly the nodes consumed from the inputs in order. When one list ends, attach the other list’s remaining suffix; it is already sorted.

The dummy node also handles empty inputs uniformly: if either input is null, the other list is returned unchanged, and if both are null, the result is null. No input nodes are copied; the result reuses every input node exactly once.

For input lengths N and M, each node is visited once, so the time complexity is O(N + M). Apart from the fixed dummy node and pointers, the auxiliary space complexity is O(1).

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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;
    }
}