Sort List
Medium · Two Pointers · Explanation and code example
Iterative Merge Sort
How it works
The recursive merge sort uses O(log n) space for the call stack. To achieve true O(1) extra space, we can implement merge sort iteratively using a bottom-up approach. Instead of recursively splitting the list, we start by treating each node as a sorted sublist of size 1, then merge adjacent pairs into sorted sublists of size 2, then 4, and so on until the entire list is sorted.
Steps
- Count the total length of the linked list.
- Use a
dummynode to simplify head management during merges. - Start with a
stepsize of1and double it each iteration until it reaches the list length. - For each
stepsize, traverse the list and split off pairs of sublists of that size. - Merge each pair of sublists and attach the merged result to the previous portion of the list.
- After all iterations complete, return the sorted list starting from
dummy.next.
Complexity
- Time complexity:
O(n log n) - Space complexity:
O(1)
Things to watch for
Incorrect Mid-Point Calculation for List Splitting
When finding the middle of the linked list, starting fast at head instead of head.next can lead to incorrect splitting, especially for lists with two elements. This causes infinite recursion as the list never gets properly divided.
Forgetting to Disconnect the Two Halves
After finding the middle node, you must set mid.next = null to properly split the list into two separate halves. Failing to disconnect them results in the merge sort operating on overlapping lists, causing incorrect results or infinite loops.
Not Handling Edge Cases for Empty or Single-Node Lists
The base case must return immediately if head is null or head.next is null. Missing this check leads to null pointer exceptions or infinite recursion when the algorithm tries to split a list that cannot be divided further.
Python code example
from typing import Optional
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
length = 0
cur = head
while cur:
length += 1
cur = cur.next
dummy = ListNode(0)
dummy.next = head
step = 1
while step < length:
prev, curr = dummy, dummy.next
while curr:
left = curr
right = self.split(left, step)
curr = self.split(right, step)
merged = self.merge(left, right)
prev.next = merged
while prev.next:
prev = prev.next
step *= 2
return dummy.next
def split(self, head, step):
if not head:
return None
for _ in range(step - 1):
if not head.next:
break
head = head.next
next_part = head.next
head.next = None
return next_part
def merge(self, list1, list2):
tail = dummy = ListNode(0)
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 or list2
return dummy.next
C++ code example
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) {
return head;
}
int length = 0;
ListNode* cur = head;
while (cur) {
length++;
cur = cur->next;
}
ListNode dummy(0);
dummy.next = head;
int step = 1;
while (step < length) {
ListNode* prev = &dummy, *curr = dummy.next;
while (curr) {
ListNode* left = curr;
ListNode* right = split(left, step);
curr = split(right, step);
ListNode* merged = merge(left, right);
prev->next = merged;
while (prev->next) {
prev = prev->next;
}
}
step *= 2;
}
return dummy.next;
}
private:
ListNode* split(ListNode* head, int step) {
if (!head) return nullptr;
for (int i = 0; i < step - 1 && head->next; i++) {
head = head->next;
}
ListNode* nextPart = head->next;
head->next = nullptr;
return nextPart;
}
ListNode* merge(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
tail->next = list1 ? list1 : list2;
return dummy.next;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.