‹ DS&A interview · Socratic
DSA · Linked List · #119

Merge Two Sorted Lists

Module 42 · difficulty 2/5·⏱ 30:00starts on first keystroke

You are given the heads of two sorted singly linked lists `list1` and `list2`. Each node has shape `{ val, next }`. Merge the two lists into one **sorted** linked list by splicing together the nodes of the original lists, and return the head of the merged list. If both lists are empty, return `null`. Implement the function `mergeTwoLists(list1, list2)`.

Examples
  • list1 = [1,2,4], list2 = [1,3,4] → [1,1,2,3,4,4] — Interleave nodes keeping non-decreasing order.
  • list1 = [], list2 = [] → [] — Both empty -> return null.
  • list1 = [], list2 = [0] → [0] — One list empty -> return the other.
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.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.