Coding Interview PatternsSort List
MediumFast and Slow Pointers

Sort List

Explanation & Solution

Practice Problem

Description

Given the head of a linked list, return the list after sorting it in ascending order.

You must solve it in O(n log n) time complexity and O(1) space complexity (ignoring recursion stack).

Input:head = [4,2,1,3]
0
4
1
2
2
1
3
3
Output:[1,2,3,4]
0
1
1
2
2
3
3
4

Explanation: The list is sorted in ascending order.

Constraints

  • The number of nodes in the list is in the range [0, 5 * 10⁴]
  • -10⁵ <= Node.val <= 10⁵

Approach

Fast and Slow Pointers pattern

1. Base Case

  • If the list is empty or has only one node, it is already sorted
  • Return the list as-is

2. Find the Middle Using Slow/Fast Pointers

  • Initialize slow to head and fast to head.next
  • Move slow one step and fast two steps at a time
  • When fast reaches the end, slow is at the middle
  • Split the list by setting slow.next = null

3. Recursively Sort Both Halves

  • Recursively call sortLinkedList on the left half (from head to slow)
  • Recursively call sortLinkedList on the right half (from mid to end)
  • Each recursive call continues splitting until single nodes remain

4. Merge Two Sorted Halves

  • Create a dummy node to build the merged list
  • Compare nodes from both lists, attaching the smaller one to the result
  • When one list is exhausted, attach the remainder of the other
  • Return dummy.next as the merged sorted list

5. Convert to Array

  • Traverse the final sorted linked list
  • Collect all values into an array and return it

Key Insight

  • This is merge sort adapted for linked lists
  • The slow/fast pointer technique finds the midpoint in O(n) without knowing the length
  • Unlike array merge sort, splitting a linked list at the middle is O(n) but merging is done in-place with pointer manipulation
Time
O(n log n)the list is split log n times, and each level of recursion does O(n) work for merging
Space
O(log n) for the recursion stack; O(1) extra space for the merge step itself

Visualization

Input:
Linked List Traversal
—
40211233null

No animation available

Slow (S)Fast (F)Both
0 steps

Solution Code

Previous
Reorder List
Next
Intersection of Two Linked Lists