Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sort List

MEDIUMProblemSolveExternal Links

Description

You are given the head of a singly linked list. Your task is to sort the linked list in ascending (non-decreasing) order and return the head of the sorted list.

A singly linked list is a data structure where each node contains a value and a pointer to the next node. Unlike arrays, you cannot access elements by index — you can only traverse from the head node forward.

The challenge here is to sort the list efficiently. A follow-up question asks whether you can achieve O(n log n) time complexity with O(1) extra space.

Examples

Example 1

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

Output: [1, 2, 3, 4]

Explanation: The original list is 4 → 2 → 1 → 3. After sorting in ascending order, the list becomes 1 → 2 → 3 → 4. Each node is rearranged so that every node's value is less than or equal to the next node's value.

Example 2

Input: head = [-1, 5, 3, 4, 0]

Output: [-1, 0, 3, 4, 5]

Explanation: The original list is -1 → 5 → 3 → 4 → 0. After sorting, the negative number comes first, followed by zero, then the positive numbers in ascending order: -1 → 0 → 3 → 4 → 5.

Example 3

Input: head = []

Output: []

Explanation: An empty list is already sorted. We simply return the empty list as is.

Constraints

  • The number of nodes in the list is in the range [0, 5 × 10^4]
  • -10^5 ≤ Node.val ≤ 10^5

Editorial

Brute Force

Intuition

The simplest way to sort a linked list is to not sort it as a linked list at all. Instead, we can extract all the node values into an array, sort the array using a built-in sorting algorithm, and then put the sorted values back into the linked list nodes.

Think of it like having a chain of numbered beads. Instead of trying to rearrange the beads on the chain (which is tricky because you can only access them one at a time), you remove all the numbers, write them on paper, sort the paper, and then put the sorted numbers back on the beads in order.

This approach leverages the power of array-based sorting algorithms (which are extremely optimized) while sidestepping the difficulty of rearranging linked list pointers.

Step-by-Step Explanation

Let's trace through with head = [4, 2, 1, 3]:

Step 1: Initialize an empty array to collect values.

  • values = []

Step 2: Traverse the linked list and extract all values.

  • Visit node 4 → values = [4]
  • Visit node 2 → values = [4, 2]
  • Visit node 1 → values = [4, 2, 1]
  • Visit node 3 → values = [4, 2, 1, 3]

Step 3: Sort the array.

  • values = [1, 2, 3, 4]

Step 4: Traverse the linked list again and overwrite each node's value with the sorted values.

  • Node 0 gets value 1
  • Node 1 gets value 2
  • Node 2 gets value 3
  • Node 3 gets value 4

Step 5: The linked list is now 1 → 2 → 3 → 4. Return the head.

Brute Force — Extract, Sort, Write Back — Watch how we collect all node values into an array, sort the array, and then write the sorted values back into the original linked list nodes.

Algorithm

  1. Initialize an empty array
  2. Traverse the linked list from head to tail, appending each node's value to the array
  3. Sort the array using a built-in sort (e.g., std::sort, sorted, Arrays.sort)
  4. Traverse the linked list again, overwriting each node's value with the corresponding sorted value from the array
  5. Return the head of the linked list

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<int> values;
        ListNode* curr = head;
        
        // Extract all values
        while (curr != nullptr) {
            values.push_back(curr->val);
            curr = curr->next;
        }
        
        // Sort the values
        sort(values.begin(), values.end());
        
        // Write sorted values back
        curr = head;
        int i = 0;
        while (curr != nullptr) {
            curr->val = values[i++];
            curr = curr->next;
        }
        
        return head;
    }
};
# 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]:
        values = []
        curr = head
        
        # Extract all values
        while curr:
            values.append(curr.val)
            curr = curr.next
        
        # Sort the values
        values.sort()
        
        # Write sorted values back
        curr = head
        for val in values:
            curr.val = val
            curr = curr.next
        
        return head
/**
 * 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) {
        List<Integer> values = new ArrayList<>();
        ListNode curr = head;
        
        // Extract all values
        while (curr != null) {
            values.add(curr.val);
            curr = curr.next;
        }
        
        // Sort the values
        Collections.sort(values);
        
        // Write sorted values back
        curr = head;
        int i = 0;
        while (curr != null) {
            curr.val = values.get(i++);
            curr = curr.next;
        }
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

We traverse the linked list once to extract values: O(n). Sorting the array takes O(n log n). Writing values back is another O(n) traversal. The dominant term is O(n log n).

Space Complexity: O(n)

We create an auxiliary array of size n to hold all the node values. This is extra space proportional to the input size.

Why This Approach Is Not Efficient

While the brute force achieves O(n log n) time, it uses O(n) extra space for the auxiliary array. This defeats one of the key advantages of linked lists — the ability to rearrange nodes by just changing pointers without needing extra memory.

The follow-up challenge explicitly asks: can we sort the list in O(n log n) time with O(1) memory? The brute force cannot achieve this because it fundamentally requires copying all values to a separate array.

Additionally, overwriting node values is considered a "cheat" in many interview settings — interviewers typically expect you to rearrange the actual nodes by manipulating their next pointers, not just swap the data stored inside them.

We need an approach that sorts the linked list by rearranging pointers directly, ideally using only constant extra space beyond the recursion stack.

Optimal Approach - Merge Sort (Top-Down)

Intuition

Merge sort is a natural fit for linked lists because its core operation — merging two sorted lists — can be done in O(1) extra space by relinking node pointers. In an array, merge sort needs a temporary buffer, but with linked lists, we simply redirect the next pointers.

The idea follows the divide-and-conquer paradigm:

  1. Divide: Split the linked list into two halves by finding the middle node using the slow/fast pointer technique.
  2. Conquer: Recursively sort each half.
  3. Combine: Merge the two sorted halves into one sorted list by comparing nodes and relinking them.

Imagine you have a long chain of shuffled playing cards. You break the chain in the middle, sort each half chain separately, then merge them together card by card, always picking the smaller card to place next. This naturally produces a fully sorted chain.

The slow/fast pointer technique works by moving one pointer one step at a time and another pointer two steps at a time. When the fast pointer reaches the end, the slow pointer is at the middle — this lets us split the list without knowing its length in advance.

Step-by-Step Explanation

Let's trace through with head = [4, 2, 1, 3]:

Step 1: Find the middle of the list [4, 2, 1, 3] using slow/fast pointers.

  • slow = node(4), fast = node(4)
  • Move: slow → node(2), fast → node(1)
  • fast.next.next is null, so stop. Middle is at slow = node(2).

Step 2: Split the list into two halves.

  • Left half: [4, 2] (head to slow)
  • Right half: [1, 3] (slow.next onwards)
  • Set slow.next = null to disconnect them.

Step 3: Recursively sort the left half [4, 2].

  • Find middle of [4, 2]: slow stops at node(4).
  • Split into [4] and [2].
  • Both are single nodes (base case), so they are already sorted.
  • Merge [4] and [2]: compare 4 vs 2 → 2 comes first → result is [2, 4].

Step 4: Recursively sort the right half [1, 3].

  • Find middle of [1, 3]: slow stops at node(1).
  • Split into [1] and [3].
  • Both are single nodes (base case), already sorted.
  • Merge [1] and [3]: compare 1 vs 3 → 1 comes first, then 3 → result is [1, 3].

Step 5: Merge the two sorted halves [2, 4] and [1, 3].

  • Compare 2 vs 1 → 1 is smaller, pick 1. Remaining: [2, 4] and [3].
  • Compare 2 vs 3 → 2 is smaller, pick 2. Remaining: [4] and [3].
  • Compare 4 vs 3 → 3 is smaller, pick 3. Remaining: [4] and [].
  • Left side exhausted? No, right is empty. Append remaining [4].
  • Result: [1, 2, 3, 4].

Step 6: Return head of sorted list: 1 → 2 → 3 → 4.

Merge Sort — Divide, Sort, and Merge a Linked List — Watch how merge sort splits the linked list in half recursively, sorts each half, and then merges them back together by relinking node pointers.

Algorithm

  1. Base case: If the list is empty or has only one node, return it (already sorted)
  2. Find the middle: Use slow/fast pointer technique — slow moves one step, fast moves two steps. When fast reaches the end, slow is at the middle.
  3. Split: Disconnect the list at the middle by setting slow.next = null. Now you have two separate lists.
  4. Recurse: Recursively call sortList on the left half and the right half.
  5. Merge: Merge the two sorted halves:
    • Use a dummy node to build the result
    • Compare the head nodes of both lists
    • Attach the smaller node to the result and advance that list's pointer
    • When one list is exhausted, append the remaining nodes of the other
  6. Return the merged sorted list

Code

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // Base case: empty or single node
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        // Find the middle using slow/fast pointers
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // Split the list into two halves
        ListNode* rightHead = slow->next;
        slow->next = nullptr;
        
        // Recursively sort both halves
        ListNode* left = sortList(head);
        ListNode* right = sortList(rightHead);
        
        // Merge the two sorted halves
        return merge(left, right);
    }
    
private:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        
        tail->next = (l1 != nullptr) ? l1 : l2;
        return dummy.next;
    }
};
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: empty or single node
        if not head or not head.next:
            return head
        
        # Find the middle using slow/fast pointers
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # Split the list into two halves
        right_head = slow.next
        slow.next = None
        
        # Recursively sort both halves
        left = self.sortList(head)
        right = self.sortList(right_head)
        
        # Merge the two sorted halves
        return self.merge(left, right)
    
    def merge(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy
        
        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 if l1 else l2
        return dummy.next
class Solution {
    public ListNode sortList(ListNode head) {
        // Base case: empty or single node
        if (head == null || head.next == null) {
            return head;
        }
        
        // Find the middle using slow/fast pointers
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Split the list into two halves
        ListNode rightHead = slow.next;
        slow.next = null;
        
        // Recursively sort both halves
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        
        // Merge the two sorted halves
        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;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

At each level of recursion, we do O(n) work total — finding the middle takes O(n/2) per sublist and merging takes O(n) per level. The recursion depth is log n because we halve the list at each step. Total: O(n) × O(log n) = O(n log n).

Space Complexity: O(log n)

The merge operation itself uses O(1) extra space (only pointer variables). However, the recursion stack depth is O(log n) because we split the list in half at each level. This is much better than the brute force's O(n) space, but technically not O(1).

For truly O(1) space, a bottom-up iterative merge sort can be used, which avoids the recursion stack entirely. The top-down recursive approach shown here is the most commonly accepted interview solution.