Skip to main content

21. Merge Two Sorted Lists

easy

Merge two sorted linked lists into one sorted list, splicing nodes from each in turn. The 'dummy head' technique introduces a pattern you'll reuse on dozens of list problems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

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.

Examples

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]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Use a dummy head so you don't special-case the first node.

Hint 2

Walk both lists with two pointers, splicing the smaller node onto the tail and advancing the corresponding pointer.

Hint 3

When one list runs out, link the rest of the other list — no extra loop needed.

Solution approach

Reveal approach

Dummy-head splice. Allocate a dummy ListNode and a tail pointer initialized to dummy. While both list1 and list2 are non-null, attach the smaller node (or list1 on tie) to tail.next, advance the corresponding source pointer, and advance tail. After the loop, exactly one of list1 or list2 may still have nodes — point tail.next at whichever is non-null (single splice, no extra loop). Return dummy.next as the merged head. O(n + m) time, O(1) extra space (we reuse the existing nodes).

Complexity

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

Related patterns

  • linked-list
  • dummy-head

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Merge Two Sorted Lists and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →