easyLinked List Essentials

Merge Two Sorted Lists

Merge two nondecreasing linked lists into one sorted linked list.

LeetCode ↗

Work through the cases

3 examples

Input notation

Each list on a separate line as space-separated values. Either line may be empty.

Expected result

Merged values separated by spaces, or empty.

Case 1

Input

1 4 8
2 3 9

Expected output

1 2 3 4 8 9

Case 2

Input

2 2
1

Expected output

1 2 2

Case 3

Input

Expected output

empty

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is to dump both lists into an array, sort, and rebuild. Total length is at most 100, so it would pass, but it throws away the fact that both lists are already sorted. The bottleneck is unnecessary reordering: each step only needs the smaller of the two heads. After taking it, what remains is still two sorted lists — the same problem, one node smaller. Compare the heads of l_1 and l_2; keep the smaller one and hang the merge of the rest on its next. When one list is empty, the other is the answer as-is. Recursion depth equals the number of nodes. Lengths here are tiny, so O(m+n) stack space is fine.

First, we judge whether the linked lists l_1 and l_2 are empty. If one of them is empty, we return the other linked list. Otherwise, we compare the head nodes of l_1 and l_2:

- If the value of the head node of l_1 is less than or equal to the value of the head node of l_2, we recursively call the function mergeTwoLists(l_1.next, l_2), and connect the head node of l_1 with the returned linked list head node, and return the head node of l_1. - Otherwise, we recursively call the function mergeTwoLists(l_1, l_2.next), and connect the head node of l_2 with the returned linked list head node, and return the head node of l_2.

The time complexity is O(m + n), and the space complexity is O(m + n). Here, m and n are the lengths of the two linked lists respectively.

/**
 * 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) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.