Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given the head of a linked list, return the list after sorting it in ascending order.
Input/Output Specifications
- Input: Head of a linked list
- Output: Head of the sorted linked list
- Constraints:
- The number of nodes in the list is in the range [0, 5 * 10^4]
- -10^5 <= Node.val <= 10^5
Examples
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: []
Solutions
Approach 1: Merge Sort (Top-Down)
This approach uses merge sort with recursion to sort the linked list.
Algorithm:
- Base case: if head is null or head.next is null, return head
- Find the middle of the list using slow and fast pointers
- Split the list into two halves
- Recursively sort both halves
- Merge the two sorted halves
- Return the merged result
Python:
def sortList(head):
"""
Sort linked list using merge sort (top-down)
Time: O(n log n)
Space: O(log n) - recursion stack
"""
if not head or not head.next:
return head
# Find the middle of the list
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Split the list into two halves
mid = slow.next
slow.next = None
# Recursively sort both halves
left = sortList(head)
right = sortList(mid)
# Merge the two sorted halves
return mergeTwoLists(left, right)
def mergeTwoLists(l1, l2):
"""Helper function to merge two sorted lists"""
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 if l1 else l2
return dummy.next
Java:
class Solution {
/**
* Sort linked list using merge sort (top-down)
* Time: O(n log n)
* Space: O(log n) - recursion stack
*/
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Find the middle of the list
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Split the list into two halves
ListNode mid = slow.next;
slow.next = null;
// Recursively sort both halves
ListNode left = sortList(head);
ListNode right = sortList(mid);
// Merge the two sorted halves
return mergeTwoLists(left, right);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
Go:
// sortList - Sort linked list using merge sort (top-down)
// Time: O(n log n)
// Space: O(log n) - recursion stack
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// Find the middle of the list
slow := head
fast := head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// Split the list into two halves
mid := slow.Next
slow.Next = nil
// Recursively sort both halves
left := sortList(head)
right := sortList(mid)
// Merge the two sorted halves
return mergeTwoLists(left, right)
}
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{Val: 0}
current := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
if l1 != nil {
current.Next = l1
} else {
current.Next = l2
}
return dummy.Next
}
JavaScript:
/**
* Sort linked list using merge sort (top-down)
* Time: O(n log n)
* Space: O(log n) - recursion stack
*/
function sortList(head) {
if (head === null || head.next === null) {
return head;
}
// Find the middle of the list
let slow = head;
let fast = head;
while (fast.next !== null && fast.next.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// Split the list into two halves
const mid = slow.next;
slow.next = null;
// Recursively sort both halves
const left = sortList(head);
const right = sortList(mid);
// Merge the two sorted halves
return mergeTwoLists(left, right);
}
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 !== null ? l1 : l2;
return dummy.next;
}
C#:
public class Solution {
/// <summary>
/// Sort linked list using merge sort (top-down)
/// Time: O(n log n)
/// Space: O(log n) - recursion stack
/// </summary>
public ListNode SortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Find the middle of the list
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Split the list into two halves
ListNode mid = slow.next;
slow.next = null;
// Recursively sort both halves
ListNode left = SortList(head);
ListNode right = SortList(mid);
// Merge the two sorted halves
return MergeTwoLists(left, right);
}
private ListNode MergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 ?? l2;
return dummy.next;
}
}
Approach 2: Merge Sort (Bottom-Up)
This approach uses iterative merge sort to avoid recursion stack space.
Algorithm:
- Start with sublists of size 1
- Merge adjacent sublists of size 1 to create sublists of size 2
- Merge adjacent sublists of size 2 to create sublists of size 4
- Continue until the entire list is sorted
- Return the sorted list
Python:
def sortListBottomUp(head):
"""
Sort linked list using merge sort (bottom-up)
Time: O(n log n)
Space: O(1)
"""
if not head or not head.next:
return head
# Count total nodes
length = 0
current = head
while current:
length += 1
current = current.next
# Start with sublists of size 1
sublist_size = 1
while sublist_size < length:
# Merge adjacent sublists
prev = None
current = head
while current:
# Get first sublist
first = current
for _ in range(sublist_size - 1):
if current.next:
current = current.next
else:
break
# Get second sublist
second = current.next
current.next = None
current = second
for _ in range(sublist_size - 1):
if current and current.next:
current = current.next
else:
break
# Store next sublist start
next_start = None
if current:
next_start = current.next
current.next = None
# Merge the two sublists
merged = mergeTwoLists(first, second)
# Connect to previous merged sublist
if prev:
prev.next = merged
else:
head = merged
# Move to end of merged sublist
while merged.next:
merged = merged.next
prev = merged
# Move to next sublist
current = next_start
sublist_size *= 2
return head
Java:
class Solution {
/**
* Sort linked list using merge sort (bottom-up)
* Time: O(n log n)
* Space: O(1)
*/
public ListNode sortListBottomUp(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Count total nodes
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// Start with sublists of size 1
int sublistSize = 1;
while (sublistSize < length) {
// Merge adjacent sublists
ListNode prev = null;
current = head;
while (current != null) {
// Get first sublist
ListNode first = current;
for (int i = 0; i < sublistSize - 1 && current.next != null; i++) {
current = current.next;
}
// Get second sublist
ListNode second = current.next;
current.next = null;
current = second;
for (int i = 0; i < sublistSize - 1 && current != null && current.next != null; i++) {
current = current.next;
}
// Store next sublist start
ListNode nextStart = null;
if (current != null) {
nextStart = current.next;
current.next = null;
}
// Merge the two sublists
ListNode merged = mergeTwoLists(first, second);
// Connect to previous merged sublist
if (prev != null) {
prev.next = merged;
} else {
head = merged;
}
// Move to end of merged sublist
while (merged.next != null) {
merged = merged.next;
}
prev = merged;
// Move to next sublist
current = nextStart;
}
sublistSize *= 2;
}
return head;
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
Go:
// sortListBottomUp - Sort linked list using merge sort (bottom-up)
// Time: O(n log n)
// Space: O(1)
func sortListBottomUp(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// Count total nodes
length := 0
current := head
for current != nil {
length++
current = current.Next
}
// Start with sublists of size 1
sublistSize := 1
for sublistSize < length {
// Merge adjacent sublists
var prev *ListNode
current = head
for current != nil {
// Get first sublist
first := current
for i := 0; i < sublistSize-1 && current.Next != nil; i++ {
current = current.Next
}
// Get second sublist
second := current.Next
current.Next = nil
current = second
for i := 0; i < sublistSize-1 && current != nil && current.Next != nil; i++ {
current = current.Next
}
// Store next sublist start
var nextStart *ListNode
if current != nil {
nextStart = current.Next
current.Next = nil
}
// Merge the two sublists
merged := mergeTwoLists(first, second)
// Connect to previous merged sublist
if prev != nil {
prev.Next = merged
} else {
head = merged
}
// Move to end of merged sublist
for merged.Next != nil {
merged = merged.Next
}
prev = merged
// Move to next sublist
current = nextStart
}
sublistSize *= 2
}
return head
}
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{Val: 0}
current := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
if l1 != nil {
current.Next = l1
} else {
current.Next = l2
}
return dummy.Next
}
JavaScript:
/**
* Sort linked list using merge sort (bottom-up)
* Time: O(n log n)
* Space: O(1)
*/
function sortListBottomUp(head) {
if (head === null || head.next === null) {
return head;
}
// Count total nodes
let length = 0;
let current = head;
while (current !== null) {
length++;
current = current.next;
}
// Start with sublists of size 1
let sublistSize = 1;
while (sublistSize < length) {
// Merge adjacent sublists
let prev = null;
current = head;
while (current !== null) {
// Get first sublist
const first = current;
for (let i = 0; i < sublistSize - 1 && current.next !== null; i++) {
current = current.next;
}
// Get second sublist
const second = current.next;
current.next = null;
current = second;
for (let i = 0; i < sublistSize - 1 && current !== null && current.next !== null; i++) {
current = current.next;
}
// Store next sublist start
let nextStart = null;
if (current !== null) {
nextStart = current.next;
current.next = null;
}
// Merge the two sublists
const merged = mergeTwoLists(first, second);
// Connect to previous merged sublist
if (prev !== null) {
prev.next = merged;
} else {
head = merged;
}
// Move to end of merged sublist
while (merged.next !== null) {
merged = merged.next;
}
prev = merged;
// Move to next sublist
current = nextStart;
}
sublistSize *= 2;
}
return head;
}
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 !== null ? l1 : l2;
return dummy.next;
}
C#:
public class Solution {
/// <summary>
/// Sort linked list using merge sort (bottom-up)
/// Time: O(n log n)
/// Space: O(1)
/// </summary>
public ListNode SortListBottomUp(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Count total nodes
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// Start with sublists of size 1
int sublistSize = 1;
while (sublistSize < length) {
// Merge adjacent sublists
ListNode prev = null;
current = head;
while (current != null) {
// Get first sublist
ListNode first = current;
for (int i = 0; i < sublistSize - 1 && current.next != null; i++) {
current = current.next;
}
// Get second sublist
ListNode second = current.next;
current.next = null;
current = second;
for (int i = 0; i < sublistSize - 1 && current != null && current.next != null; i++) {
current = current.next;
}
// Store next sublist start
ListNode nextStart = null;
if (current != null) {
nextStart = current.next;
current.next = null;
}
// Merge the two sublists
ListNode merged = MergeTwoLists(first, second);
// Connect to previous merged sublist
if (prev != null) {
prev.next = merged;
} else {
head = merged;
}
// Move to end of merged sublist
while (merged.next != null) {
merged = merged.next;
}
prev = merged;
// Move to next sublist
current = nextStart;
}
sublistSize *= 2;
}
return head;
}
private ListNode MergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 ?? l2;
return dummy.next;
}
}
Key Insights
- Merge sort: Optimal sorting algorithm for linked lists
- Divide and conquer: Split list in half, sort each half, then merge
- Space complexity: Top-down uses O(log n) recursion stack, bottom-up uses O(1)
- Time complexity: O(n log n) in both cases
- Stable sort: Maintains relative order of equal elements
Edge Cases
- Empty list
- Single node list
- Two node list
- Already sorted list
- Reverse sorted list
- List with duplicate values
Test Cases
# Test case 1: Normal case
head1 = ListNode(4)
head1.next = ListNode(2)
head1.next.next = ListNode(1)
head1.next.next.next = ListNode(3)
# sortList(head1) -> [1,2,3,4]
# Test case 2: Already sorted
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
# sortList(head2) -> [1,2,3]
# Test case 3: Reverse sorted
head3 = ListNode(3)
head3.next = ListNode(2)
head3.next.next = ListNode(1)
# sortList(head3) -> [1,2,3]
# Test case 4: Single node
head4 = ListNode(1)
# sortList(head4) -> [1]
Follow-up Questions
- How would you handle very large lists?
- Can you solve this with O(1) space?
- How would you handle lists with duplicate values?
- What if you need to sort in descending order?
Common Mistakes
- Not handling empty lists properly
- Incorrect middle finding algorithm
- Not properly splitting the list
- Incorrect merge implementation
- Memory leaks when not properly managing pointers
- Off-by-one errors in sublist size calculation