Sort List - Video Solutions

Problem Overview: Given the head of a singly linked list, you must return the list sorted in ascending order. The challenge is sorting efficiently while working with linked list constraints—no random access and minimal extra space.

Approach 1: Copy to Array and Sort (O(n log n) time, O(n) space)

The simplest strategy converts the linked list into an array, sorts the array using a standard algorithm like quicksort or mergesort, and then rebuilds the linked list. You iterate through the list once to collect values, apply the built-in array sort, then iterate again to recreate nodes in sorted order. This approach works because arrays support efficient sorting and random access. However, it uses O(n) additional memory and ignores the structural advantages of a linked list, so it’s rarely the preferred interview solution.

Approach 2: Merge Sort on Linked List (O(n log n) time, O(log n) space)

Merge sort is the natural fit for linked lists. The algorithm repeatedly splits the list into two halves using the fast and slow pointer technique, a classic two pointers pattern. Each half is recursively sorted, then merged using a standard sorted-merge routine that compares node values and relinks pointers. Because merging two linked lists only requires pointer updates, it runs in linear time. The recursion depth contributes O(log n) stack space. This divide and conquer strategy guarantees O(n log n) time while avoiding expensive node reallocations.

Approach 3: Bottom-Up Merge Sort (O(n log n) time, O(1) space)

The bottom-up version removes recursion and performs iterative merges. You start by merging pairs of nodes (size = 1), then merge sorted blocks of size 2, 4, 8, and so on until the entire list is sorted. Each pass walks the list, splitting segments and merging them in place. Since it doesn’t rely on recursive calls, the algorithm maintains constant auxiliary space while preserving the same O(n log n) time complexity. This approach is commonly labeled as merge sort optimized for linked lists and is the most space-efficient implementation.

Recommended for interviews: Top-down merge sort is the most common answer. It clearly demonstrates understanding of linked list traversal, splitting with fast/slow pointers, and merging sorted lists. Bottom-up merge sort is even more optimal in space, but interviewers usually expect the recursive version unless the problem explicitly asks for constant space.