Skip to main content

21. Merge Two Sorted Lists

easyAsked at Cohere

Merge two sorted linked lists into one sorted list. Cohere values this because the merge step is the backbone of k-way merge used when combining ranked candidate lists from multiple retrieval indexes in RAG pipelines.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2025-Q4)— Cohere SWE interviewees report merge-two-sorted-lists as an easy warm-up before harder linked-list questions.
  • Blind (2025-10)— Cohere candidate prep threads list this as expected easy linked-list knowledge.

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: Nodes are interleaved in sorted order.

Example 2

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

Explanation: Both empty — return null.

Example 3

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

Explanation: One list empty — return the other.

Approaches

1. Iterative with dummy head

Use a dummy head node to simplify edge cases. Walk both lists simultaneously, attaching the smaller node to the result.

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

Tradeoff: O(m+n) time, O(1) space — optimal. The dummy head eliminates special-casing for the initial node.

2. Recursive

Compare heads; recurse on the tail of the smaller list.

Time
O(m + n)
Space
O(m + n) call stack
function mergeTwoLists(list1, list2) {
  if (list1 === null) return list2;
  if (list2 === null) 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 O(m+n) stack depth. Safe for the given constraints (max 100 nodes); risky for production-scale lists.

Cohere-specific tips

Cohere may extend this to Merge K Sorted Lists — the k-way merge of ranked document chunks from a retrieval index. State this connection explicitly: 'This two-list merge is the inner step of k-way merge sort, and k-way merge is exactly how re-ranking pipelines combine results from multiple retrieval shards.' Then transition naturally to a heap-based approach for the k-list variant.

Common mistakes

  • Not attaching the remaining tail — when one list is exhausted, the other's remaining nodes must be appended wholesale.
  • Modifying node values instead of rewiring pointers — the problem asks to splice existing nodes.
  • Forgetting to handle both-empty input — should return null cleanly.
  • Advancing both pointers when only one should move forward.

Follow-up questions

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

  • Merge K Sorted Lists — use a min-heap for O((n·k) log k) time.
  • Sort List — merge sort a linked list in O(n log n) time O(1) space.
  • How would you merge k sorted streams arriving from different retrieval shards?

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 does the dummy head simplify the code?

Without it, the first node attachment requires a special case to initialise the result head. The dummy makes every attachment uniform.

Does the iterative approach create new nodes?

No — it rewires the next pointers of existing nodes. Space is O(1) beyond the dummy node.

What if the lists have different lengths?

The remaining tail of the longer list is attached wholesale at the end — no additional traversal needed because both lists are already sorted.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →