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

Sort List

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

Given the `head` of a singly linked list, sort the list in **ascending** order by node value and return the head of the sorted list. Each node has shape `{ val: number, next: ListNode | null }`. Implement `sortList(head)` returning the new head. Aim for O(n log n) time. Re-link the existing nodes; do not allocate a new array of values as the intended solution.

Examples
  • head = [4,2,1,3] → [1,2,3,4] — Values sorted ascending.
  • head = [-1,5,3,4,0] → [-1,0,3,4,5] — Handles negative values.
  • head = [] → [] — Empty list returns null.
Constraints
  • · The number of nodes is in the range [0, 5 * 10^4].
  • · -10^5 <= Node.val <= 10^5
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.