Sort List solution and explanation
Google
9 more videos on this problem
Sort List - Merge Sort - Leetcode 148NeetCode · 13:17 · 102K views
Sort List | Leetcode 148 | Linked List | Day-24Ayushi Sharma · 15:12 · 33K views
[Java] Leetcode 148. Sort List [LinkedList #9]Eric Programming · 7:03 · 4K views
Sort List | Leet code 148 | Theory explained + Python codeSai Anish Malla · 24:59 · 2K views
LeetCode 148 | Sort List | Solution Explained (Java + Whiteboard)Xavier Elon · 13:51 · 2K views
Sort List | Leetcode148 | Live coding session 🔥🔥 | Merge Sort over Linkedin ListCoding Decoded · 12:02 · 1K views
Sort List Leetcode 148 video | leetcode solutionEasyLeetcode · 5:32 · 963 views
Sort List Solution -- Leetcode Question 148 Solution With Code (Java)Alex Solves Algorithms · 15:43 · 772 views
Sort List | Leetcode 148 | LinkedList | Divide&Conquer | MergeSortNitesh Nanda · 16:18 · 653 views
LEETCODE 148 SORT LINKED LIST PYTHON | Merge sortSasa codes · 10:37 · 385 views
The problem
Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Input: head = [4,2,1,3] Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]
Example 3:
Input: head = [] Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 104]. -105 <= Node.val <= 105
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Approach overview
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.
Approach 1: Merge Sort on Linked List
This approach leverages the merge sort algorithm, which is well-suited for linked lists compared to arrays. The merge sort algorithm uses a divide-and-conquer strategy: it splits the list in half recursively until it can no longer be divided, and then merges the sublists back together in sorted order.
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
# split the linked list in half
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid, slow.next = slow.next, None
# sort each half
left, right = self.sortList(head), self.sortList(mid)
# merge the sorted halves
return self.merge(left, right)
def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = tail = ListNode(None)
while l1 and l2:
if l1.val < l2.val:
tail.next, l1 = l1, l1.next
else:
tail.next, l2 = l2, l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.nextpublic ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow->next;
slow->next = nullptr;
ListNode* left = sortList(head);
ListNode* right = sortList(mid);
return merge(left, right);
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}var sortList = function(head) {
if (!head || !head.next) return head;
let slow = head, fast = head.next;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let mid = slow.next;
slow.next = null;
let left = sortList(head);
let right = sortList(mid);
return merge(left, right);
};
function merge(l1, l2) {
let dummy = new ListNode(0);
let tail = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 || l2;
return dummy.next;
}struct ListNode* sortList(struct ListNode* head) {
// base case
if (!head || !head->next) return head;
// split list into halves
struct ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
struct ListNode* mid = slow->next;
slow->next = NULL;
// recursively sort the sublists
struct ListNode* left = sortList(head);
struct ListNode* right = sortList(mid);
// merge both halves
return merge(left, right);
}
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy;
struct ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}public ListNode SortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
ListNode left = SortList(head);
ListNode right = SortList(mid);
return Merge(left, right);
}
private ListNode Merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}The Python approach begins by checking for base cases and then proceeds to divide the list using a two-pointer method. The sorting and merging processes are handled by recursive calls, ensuring the list is sorted and merged efficiently.
Time Complexity: O(n log n) where n is the number of nodes in the list. Space Complexity: O(log n) for recursion stack.
Approach 2: Bottom-Up Merge Sort for Linked List
This approach implements an iterative, bottom-up merge sort, avoiding the recursion and thus achieving O(1) space complexity beyond the input and output list. The list isn't split recursively but is treated progressively as sublists of increasing sizes are sorted and merged.
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
dummy = ListNode(0)
dummy.next = head
length, step = 0, 1
while head:
head = head.next
length += 1
while step < length:
curr, tail = dummy.next, dummy
while curr:
left = curr
right = self.split(left, step)
curr = self.split(right, step)
tail = self.merge(tail, left, right)
step <<= 1
return dummy.next
def split(self, head: ListNode, step: int) -> ListNode:
for i in range(1, step):
if head:
head = head.next
if not head:
return None
second, head.next = head.next, None
return second
def merge(self, tail: ListNode, l1: ListNode, l2: ListNode) -> ListNode:
cur = tail
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
while cur.next:
cur = cur.next
return curpublic ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode tail, left, right;
int n = 0, step = 1;
for (ListNode node = head; node != null; node = node.next) n++;
for (step = 1; step < n; step <<= 1) {
ListNode cur = dummy.next;
tail = dummy;
while (cur != null) {
left = cur;
right = split(left, step);
cur = split(right, step);
tail = merge(tail, left, right);
}
}
return dummy.next;
}
private ListNode split(ListNode head, int step) {
for (int i = 1; head != null && i < step; i++) head = head.next;
if (head == null) return null;
ListNode second = head.next;
head.next = null;
return second;
}
private ListNode merge(ListNode tail, ListNode l1, ListNode l2) {
ListNode cur = tail;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
while (cur.next != null) cur = cur.next;
return cur;
}ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode dummy(0);
dummy.next = head;
ListNode* tail;
ListNode* left;
ListNode* right;
int n = 0, step = 1;
for (ListNode* node = head; node; node = node->next) n++;
for (step = 1; step < n; step <<= 1) {
ListNode* cur = dummy.next;
tail = &dummy;
while (cur) {
left = cur;
right = split(left, step);
cur = split(right, step);
tail = merge2(tail, left, right);
}
}
return dummy.next;
}
ListNode* split(ListNode* head, int step) {
for (int i = 1; head && i < step; ++i) head = head->next;
if (!head) return nullptr;
ListNode* second = head->next;
head->next = nullptr;
return second;
}
ListNode* merge2(ListNode* tail, ListNode* l1, ListNode* l2) {
ListNode* cur = tail;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
while (cur->next) cur = cur->next;
return cur;
}var sortList = function(head) {
if (!head || !head.next) return head;
let dummy = new ListNode(0, head);
let length = 0, step = 1;
for (let node = head; node; node = node.next) length++;
while (step < length) {
let cur = dummy.next, tail = dummy;
while (cur) {
let left = cur;
let right = split(left, step);
cur = split(right, step);
tail = merge(tail, left, right);
}
step <<= 1;
}
return dummy.next;
};
function split(head, step) {
for (let i = 1; head && i < step; i++) {
head = head.next;
}
if (!head) return null;
let second = head.next;
head.next = null;
return second;
}
function merge(tail, l1, l2) {
while (l1 && l2) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 || l2;
while (tail.next) tail = tail.next;
return tail;
}struct ListNode* sortList(struct ListNode* head) {
if (!head || !head->next) return head;
int n = 0;
struct ListNode* node = head;
while (node) {
node = node->next;
n++;
}
struct ListNode dummy;
dummy.next = head;
for (int step = 1; step < n; step <<= 1) {
struct ListNode* prev = &dummy;
struct ListNode* cur = dummy.next;
while (cur) {
struct ListNode* left = cur;
struct ListNode* right = split(left, step);
cur = split(right, step);
prev = merge2(prev, left, right);
}
}
return dummy.next;
}
struct ListNode* split(struct ListNode* head, int step) {
for (int i = 1; head && i < step; i++) {
head = head->next;
}
if (!head) return NULL;
struct ListNode* second = head->next;
head->next = NULL;
return second;
}
struct ListNode* merge2(struct ListNode* prev, struct ListNode* l1, struct ListNode* l2) {
struct ListNode* cur = prev;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
while (cur->next) cur = cur->next;
return cur;
}public ListNode SortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(0), tail;
dummy.next = head;
int length = 0, step = 1;
for (ListNode node = head; node != null; node = node.next) length++;
while (step < length) {
ListNode cur = dummy.next;
tail = dummy;
while (cur != null) {
ListNode left = cur;
ListNode right = Split(left, step);
cur = Split(right, step);
tail = Merge(tail, left, right);
}
step <<= 1;
}
return dummy.next;
}
private ListNode Split(ListNode head, int step) {
for (int i = 1; head != null && i < step; i++) head = head.next;
if (head == null) return null;
ListNode second = head.next;
head.next = null;
return second;
}
private ListNode Merge(ListNode tail, ListNode l1, ListNode l2) {
ListNode cur = tail;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 ?? l2;
while (cur.next != null) cur = cur.next;
return cur;
}The Python version uses a bottom-up approach with a dummy node to assist with list organization during merging. It iteratively increases the step size while using split/merge operations to handle list parts.
Time Complexity: O(n log n), Space Complexity: O(1) if we consider manipulating the linked list in place.
Approach 3: Merge Sort
We can use the merge sort approach to solve this problem.
First, we use the fast and slow pointers to find the middle of the linked list and break the list from the middle to form two separate sublists l1 and l2.
Then, we recursively sort l1 and l2, and finally merge l1 and l2 into a sorted linked list.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function sortList(head: ListNode | null): ListNode | null {
if (head === null || head.next === null) {
return head;
}
let [slow, fast] = [head, head.next];
while (fast !== null && fast.next !== null) {
slow = slow.next!;
fast = fast.next.next;
}
let [l1, l2] = [head, slow.next];
slow.next = null;
l1 = sortList(l1);
l2 = sortList(l2);
const dummy = new ListNode();
let tail = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 ?? l2;
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
l1 := head
l2 := slow.Next
slow.Next = nil
l1 = sortList(l1)
l2 = sortList(l2)
dummy := &ListNode{}
tail := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
tail.Next = l1
l1 = l1.Next
} else {
tail.Next = l2
l2 = l2.Next
}
tail = tail.Next
}
if l1 != nil {
tail.Next = l1
} else {
tail.Next = l2
}
return dummy.Next
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
fn merge(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match (l1, l2) {
(None, Some(node)) | (Some(node), None) => Some(node),
(Some(mut node1), Some(mut node2)) => {
if node1.val < node2.val {
node1.next = merge(node1.next.take(), Some(node2));
Some(node1)
} else {
node2.next = merge(Some(node1), node2.next.take());
Some(node2)
}
}
_ => None,
}
}
fn sort(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if head.is_none() || head.as_ref().unwrap().next.is_none() {
return head;
}
let mut head = head;
let mut length = 0;
let mut cur = &head;
while cur.is_some() {
length += 1;
cur = &cur.as_ref().unwrap().next;
}
let mut cur = &mut head;
for _ in 0..length / 2 - 1 {
cur = &mut cur.as_mut().unwrap().next;
}
let right = cur.as_mut().unwrap().next.take();
merge(sort(head), sort(right))
}
sort(head)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Merge Sort on Linked List | Time Complexity: O(n log n) where n is the number of nodes in the list. Space Complexity: O(log n) for recursion stack. |
| Bottom-Up Merge Sort for Linked List | Time Complexity: O(n log n), Space Complexity: O(1) if we consider manipulating the linked list in place. |
| Merge Sort | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Copy List to Array and Sort | O(n log n) | O(n) | Quick implementation when extra memory is acceptable |
| Top-Down Merge Sort | O(n log n) | O(log n) | Standard interview solution for sorting linked lists |
| Bottom-Up Merge Sort | O(n log n) | O(1) | Best when constant extra space is required |
Frequently asked questions
Is Sort List easy or hard?
Sort List is generally classified as a medium-level problem. The main challenge is implementing merge sort directly on a linked list without converting it to an array. Understanding pointer manipulation and list splitting makes the solution straightforward.
Sort List Python/Java solution
Python and Java implementations typically use merge sort for linked lists. The algorithm finds the midpoint using fast and slow pointers, recursively sorts both halves, and merges them using pointer comparisons. This keeps the runtime at O(n log n) with minimal extra space.
How to solve Sort List in O(n)?
Sorting a general linked list in O(n) time is not possible without constraints on the input values. Comparison-based sorting requires at least O(n log n). Merge sort achieves this optimal bound while keeping pointer operations efficient for linked lists.
What is the best approach for Sort List?
Merge sort on a linked list is the optimal approach. It splits the list into halves using fast and slow pointers, recursively sorts each half, and merges them. This guarantees O(n log n) time complexity while working efficiently with pointer-based structures.
Is Sort List asked at Google/Amazon/Meta?
Sort List is a common interview problem across major tech companies including Amazon, Google, and Meta. It tests knowledge of linked list manipulation, merge sort, and fast-slow pointer techniques. Variants often appear in coding interviews focused on data structures.
What data structure is used in Sort List?
The problem operates on a singly linked list. Efficient solutions rely on pointer manipulation, splitting the list with two pointers, and merging sorted linked lists. No additional complex data structures are required beyond temporary pointer references.
What is the time complexity of Sort List?
The optimal solution runs in O(n log n) time. Merge sort divides the list into halves recursively and merges sorted sublists in linear time. Since there are log n levels of splitting and each level processes n nodes, the total complexity becomes O(n log n).