How do you approach Merge Two Sorted Lists?

Use two pointers, one for each list.

What is the time complexity of Merge Two Sorted Lists?

Time complexity: O(n + m) where n and m are the lengths of the two lists. Space complexity: O(n + m) for the result array.

What are common mistakes on Merge Two Sorted Lists?

Reassigning next before saving it, which loses the rest of the list. Skipping the dummy head, which forces a special case every time the real head changes. Advancing the fast pointer without checking both fast and fast.next - the null dereference only shows up on even-length lists.

gitGood.dev

← Back to problems

Merge Two Sorted Lists

EasyData Structures

Description

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Note: For this problem, linked lists are represented as arrays for simplicity. The function should return a merged sorted array.

Example 1

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

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

Example 2

Input: list1 = [], list2 = []

Output: []

Example 3

Input: list1 = [], list2 = [0]

Output: [0]

Constraints

- The number of nodes in both lists is in the range [0, 50]. - -100 <= Node.val <= 100 - Both list1 and list2 are sorted in non-decreasing order.

Merge Two Sorted Lists: approach, complexity and pitfalls

An easy linked list problem, graded against 6 test cases (3 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

Use two pointers, one for each list.
Compare elements at both pointers and add the smaller one to the result.
Don't forget to add remaining elements when one list is exhausted.

The optimal approach

Show the approach: Two Pointers

Use two pointers to traverse both lists, always picking the smaller element.

Time: O(n + m) where n and m are the lengths of the two lists
Space: O(n + m) for the result array

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.