Skip to main content

21. Merge Two Sorted Lists

easyAsked at AMD

Merge two sorted linked lists into one sorted list. AMD uses this to test pointer manipulation and dummy-node technique — the same pattern appears in hardware sorted-merge units, priority queues in task schedulers, and merge phases of external sort in GPU memory.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2025-12)— AMD SWE interviewers include Merge Two Sorted Lists as a standard linked-list pointer problem in early rounds.
  • Blind (2025-09)— AMD prep threads flag this as a common easy that also tests clean code style — dummy head node usage noted.

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]

Explanation: Elements interleaved in sorted order.

Example 2

Input
list1 = [], list2 = []
Output
[]

Explanation: Both empty, result is empty.

Example 3

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

Explanation: One empty list, result is the other.

Approaches

1. Iterative with dummy head

Use a dummy sentinel node to avoid special-casing the head. Advance a tail pointer, always appending the smaller of the two current nodes.

Time
O(m + n)
Space
O(1)
function mergeTwoLists(list1, list2) {
  const dummy = { next: null };
  let tail = dummy;
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }
  tail.next = list1 || list2; // append remaining
  return dummy.next;
}

Tradeoff: O(1) extra space — no new nodes, just pointer rewiring. The dummy node eliminates edge-case handling for the first element.

2. Recursive

Compare heads, attach the smaller, and recurse on the rest.

Time
O(m + n)
Space
O(m + n) call stack
function mergeTwoLists(list1, list2) {
  if (!list1) return list2;
  if (!list2) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

Tradeoff: Elegant but uses O(m+n) call stack. For the deep lists that could appear in hardware queue merging, the iterative version is safer.

AMD-specific tips

AMD task schedulers and GPU command queues merge sorted priority lists constantly. Mention the dummy-head technique explicitly: 'using a sentinel node means I never special-case the first insertion — every node is appended the same way.' This is idiomatic C-style pointer programming that AMD firmware engineers use. The `tail.next = list1 || list2` line to append the remaining segment is a clean one-liner worth calling out.

Common mistakes

  • Returning dummy instead of dummy.next — the dummy node is a sentinel, not part of the output.
  • Not handling one empty list — if list1 or list2 is null from the start, the while loop never runs, and tail.next = the non-null list is correct.
  • Creating new nodes instead of rewiring pointers — the problem says splice, not copy.
  • Forgetting to advance tail after each attachment — tail stays at the same node forever.

Follow-up questions

An interviewer at AMD may pivot to one of these next:

  • Merge K Sorted Lists (LC 23) — generalize to k lists using a min-heap.
  • Sort List (LC 148) — sort a linked list using merge sort.
  • How would you merge two sorted arrays in-place? (Two-pointer from the end.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why use a dummy head node?

It eliminates the special case of setting the head of the result. Without it, you'd need an if-else to initialize the head before the loop. With a dummy, every node is appended identically.

Is the list stable (equal elements keep their original order)?

Yes — when values are equal, we take from list1 first (list1.val <= list2.val). If stability is required, this is the correct choice.

Practice these live with InterviewChamp.AI

Drill Merge Two Sorted Lists and other AMD interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →