DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All interview questions

Interview preparation

Merge Two Sorted Lists

EasyLinked ListsRecursion
AmazonMicrosoftAppleAdobe Community-reported practice tags — not verified company questions.

1Problem statement

Merge two sorted linked lists into one sorted list made by splicing together the nodes of the two lists, and return its head.

2Examples

Input: list1 = 1 → 2 → 4, list2 = 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4
Input: list1 = empty, list2 = 0
Output: 0

3Constraints

  • 0 ≤ length of each list ≤ 50
  • Both lists are sorted in non-decreasing order.

4Approaches

Approach 1

Brute Force

Collect all values, sort them, build a new list.

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

Approach 2

Better: Recursion

The smaller head comes first; its next is the merge of the rest.

Time O(m+n)Space O(m+n) call stack

Approach 3

Optimal: Iterative with a dummy node

Keep a tail pointer; always attach the smaller current node, then append the leftover list.

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

5Code (optimal approach)

Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeTwoLists(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a !== null && b !== null) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a !== null ? a : b;
  return dummy.next;
}

function build(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head);
  return head;
}

function show(head) {
  const out = [];
  for (let n = head; n !== null; n = n.next) out.push(n.val);
  out.push("null");
  return out.join(" -> ");
}

console.log(show(mergeTwoLists(build([1, 2, 4]), build([1, 3, 4]))));
console.log(show(mergeTwoLists(build([]), build([0]))));

6Complexity

Time

O(m + n)

Space

O(1)

7Visual walkthrough

  1. 1.dummy → ; compare 1 and 1 → take list1's 1
  2. 2.compare 2 and 1 → take 1
  3. 3.compare 2 and 3 → take 2
  4. 4.compare 4 and 3 → take 3
  5. 5.compare 4 and 4 → take 4, then append remaining 4

Related visualization (Singly Linked List Insertion) — shows the core data-structure operations this solution relies on:

Singly Linked List Insertioninteractive Open full visualizer
head
10
[0]
20
[1]
30
[2]
tail
40
[3]
null
current pointernew nodeinserted

Inserts a new node at a given position: walk to the node just before the position, point the new node at its successor, then re-link the predecessor to the new node.

1 / 11

8Related questions

Reverse Linked List

On this page

  1. 01Problem statement
  2. 02Examples
  3. 03Constraints
  4. 04Approaches
  5. 05Code (4 languages)
  6. 06Complexity
  7. 07Visual walkthrough
  8. 08Related questions