Linked List · 021Easy
Merge Two Sorted Lists
You are given the heads of two sorted linked lists. Splice them together into one sorted list and return its head. The result must reuse the existing nodes.
Constraints
- Each list holds 0 to 50 nodes.
- -100 <= Node.val <= 100
- Both lists are sorted ascending.
- INPUT FORMAT
- `head` is a ListNode object, not an array. The arrays in EXAMPLES list the node values in
- order; the test runner links them into real nodes before calling your function.
Examples
mergeTwoLists(1 -> 2 -> 4, 1 -> 3 -> 4) -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 mergeTwoLists(null, null) -> null mergeTwoLists(null, 0) -> 0 mergeTwoLists(1 -> 2 -> 3, null) -> 1 -> 2 -> 3 // remainder attached as-is mergeTwoLists(2 -> 2, 2 -> 2) -> 2 -> 2 -> 2 -> 2 // duplicates across lists mergeTwoLists(-100 -> -50, -75 -> 0 -> 100) -> -100 -> -75 -> -50 -> 0 -> 100
Edge cases
- Either or both lists empty.
- Duplicate values across lists.
Show the target complexity (spoiler)
- Naive
- O((m+n) log(m+n)) time — concatenate then sort, discarding the sorted structure.
- Target
- O(m + n) time, O(1) space — a dummy head node plus two pointers, always taking the smaller front node.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/06-linked-list/021-merge-two-sorted-lists.js ./practice c 021