# Sort List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sort-list)
Canonical: https://scaleengineer.com/dsa/problems/sort-list
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Sorting](https://scaleengineer.com/algorithms/sorting), [Merge Sort](https://scaleengineer.com/algorithms/merge-sort)
**Data structures:** Linked List
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Oracle](https://scaleengineer.com/companies/oracle), [TikTok](https://scaleengineer.com/companies/tiktok), [Yahoo](https://scaleengineer.com/companies/yahoo), [Lyft](https://scaleengineer.com/companies/lyft), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
Given the `head` of a linked list, return _the list after sorting it in **ascending order**_.

**Example 1:**

![](https://assets.glich.co/dsa/sort-list/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/sort-list/image1.jpg) 

**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)?

# Approaches
## Brute Force using Selection Sort
A simple but inefficient approach is to use a sorting algorithm with O(n^2) time complexity, like Selection Sort. We can iterate through the list, and for each node, find the node with the minimum value in the rest of the list and swap their values. This process is repeated for every node.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; In-place sorting with constant extra space.
**Cons:** Very slow for large lists and will likely result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
This method iterates through the linked list, treating the current position as the position to place the next smallest element. For each position `current`, it scans the remainder of the list (`runner`) to find the node with the minimum value. Once found, the value of the `current` node is swapped with the value of the minimum node. This ensures that the prefix of the list up to `current` is sorted relative to the elements within that prefix. The outer loop moves `current` one step forward at a time, extending the sorted portion of the list until the entire list is sorted.

```java
/**
 * 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 == null) {
            return null;
        }
        ListNode current = head;
        while (current != null) {
            ListNode minNode = current;
            ListNode runner = current.next;
            while (runner != null) {
                if (runner.val < minNode.val) {
                    minNode = runner;
                }
                runner = runner.next;
            }
            // Swap values
            int temp = current.val;
            current.val = minNode.val;
            minNode.val = temp;
            
            current = current.next;
        }
        return head;
    }
}
```
### Algorithm
- Start with a pointer `current` at the head of the list.
- While `current` is not null:
  - Create another pointer `runner` starting from `current.next`.
  - Find the node with the minimum value in the sublist starting from `current`. Let's call it `minNode`.
  - Swap the value of `current` with the value of `minNode`.
  - Move `current` to `current.next`.
- Return the head of the list.

## Convert to Array and Sort
A straightforward approach is to leverage the efficiency of array-based sorting algorithms. We can traverse the linked list, store its values in an array, sort the array, and then iterate through the list again to update the node values from the sorted array.
**Time:** O(n log n) · **Space:** O(n)
**Pros:** Relatively easy to implement.; Leverages highly optimized built-in sorting functions.
**Cons:** Requires O(n) extra space to store the list values, which does not meet the follow-up constraint of O(1) space.
### Explanation
This method decouples the sorting logic from the linked list structure. First, the linked list is converted into a more sort-friendly data structure, an array. This takes O(n) time. Then, a standard, highly optimized sorting algorithm (like Timsort, used by `Collections.sort` in Java) is applied to the array, which takes O(n log n) time. Finally, the sorted values from the array are copied back into the original linked list nodes by traversing the list one more time. This final step also takes O(n) time. The overall time complexity is dominated by the sorting step.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 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 == null || head.next == null) {
            return head;
        }
        
        List<Integer> values = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }
        
        Collections.sort(values);
        
        current = head;
        int i = 0;
        while (current != null) {
            current.val = values.get(i++);
            current = current.next;
        }
        
        return head;
    }
}
```
### Algorithm
- Handle the edge case where the list is empty or has one node.
- Create a dynamic array (like `ArrayList` in Java).
- Iterate through the linked list from head to tail, adding each node's value to the array.
- Sort the array using a built-in sorting function, which typically has a time complexity of O(n log n).
- Initialize a pointer `current` to the head of the list.
- Iterate through the sorted array, updating the value of each node in the linked list with the corresponding element from the array.
- Return the original head of the list, which now contains sorted values.

## Top-Down Merge Sort (Recursive)
Merge Sort is a divide-and-conquer algorithm that is well-suited for linked lists. This approach recursively splits the list into two halves, sorts them independently, and then merges the two sorted halves.
**Time:** O(n log n) · **Space:** O(log n)
**Pros:** Achieves the optimal O(n log n) time complexity.; Conceptually elegant and a classic divide-and-conquer example.
**Cons:** The recursion stack uses O(log n) space, which does not satisfy the O(1) space follow-up constraint.
### Explanation
This approach implements the classic Merge Sort algorithm. The main function `sortList` first checks for the base case (a list of size 0 or 1). If not the base case, it finds the middle of the list using a helper function `getMid`. This function uses two pointers, `slow` and `fast`, where `fast` moves twice as fast as `slow`. When `fast` reaches the end, `slow` is at the middle. The list is then split into two sublists, `left` and `right`. The function then calls itself recursively on these two sublists. The returned sorted sublists are then merged by a `merge` helper function. The `merge` function takes two sorted lists and combines them into a single sorted list by iteratively picking the smaller of the two heads.

```java
/**
 * 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 == null || head.next == null) {
            return head;
        }
        
        // Step 1: Split the list into two halves
        ListNode mid = getMid(head);
        ListNode left = head;
        ListNode right = mid.next;
        mid.next = null;
        
        // Step 2: Sort each half
        left = sortList(left);
        right = sortList(right);
        
        // Step 3: Merge the sorted halves
        return merge(left, right);
    }
    
    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null) ? list1 : list2;
        return dummyHead.next;
    }
    
    private ListNode getMid(ListNode head) {
        ListNode midPrev = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            midPrev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        return midPrev;
    }
}
```
### Algorithm
- **Base Case:** If the list is empty or has only one node, it's already sorted, so return it.
- **Split:** Find the middle of the linked list using the 'slow and fast pointer' technique. Split the list into two halves at the middle.
- **Recurse:** Recursively call the sort function on both halves.
- **Merge:** Merge the two sorted halves into a single sorted list and return its head.

## Bottom-Up Merge Sort (Constant Space)
This is the most optimal approach, satisfying both the O(n log n) time and O(1) space constraints. It's an iterative version of Merge Sort. Instead of recursively splitting the list from the top down, it starts by merging small sublists of size 1 and iteratively merges them into larger sorted sublists until the entire list is sorted.
**Time:** O(n log n) · **Space:** O(1)
**Pros:** Most efficient solution.; Meets the time (O(n log n)) and space (O(1)) complexity requirements of the follow-up question.
**Cons:** Significantly more complex to understand and implement correctly compared to the recursive version.
### Explanation
This bottom-up approach avoids recursion and its associated space overhead. It works by making multiple passes over the list. In the first pass, it merges sublists of size 1 to produce sorted sublists of size 2. In the second pass, it merges sorted sublists of size 2 to produce sorted sublists of size 4, and so on. This continues until the sublist size is greater than or equal to the list's length.

A `dummy` node is used to simplify handling the head of the list. In each pass (controlled by `size`), we iterate through the list, splitting it into a `left` part and a `right` part, each of at most `size` nodes. These two parts are then merged, and the resulting sorted list is appended to the tail of the list sorted so far. This process is repeated until all nodes for the current pass are merged.

```java
/**
 * 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 == null || head.next == null) {
            return head;
        }

        int n = 0;
        ListNode curr = head;
        while (curr != null) {
            n++;
            curr = curr.next;
        }

        ListNode dummy = new ListNode(0, head);
        for (int size = 1; size < n; size <<= 1) {
            ListNode tail = dummy;
            curr = dummy.next;
            while (curr != null) {
                ListNode left = curr;
                ListNode right = split(left, size);
                curr = split(right, size);

                tail.next = merge(left, right);
                while (tail.next != null) {
                    tail = tail.next;
                }
            }
        }
        return dummy.next;
    }

    private ListNode split(ListNode head, int size) {
        if (head == null) return null;
        for (int i = 1; i < size && head.next != null; i++) {
            head = head.next;
        }
        ListNode secondHead = head.next;
        head.next = null;
        return secondHead;
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null) ? list1 : list2;
        return dummyHead.next;
    }
}
```
### Algorithm
- First, calculate the length `n` of the linked list.
- Create a `dummy` node and point its `next` to the `head`.
- Start an outer loop for the sublist size `size`, from 1 to `n`, doubling it in each iteration (`size = 1, 2, 4, ...`).
- Inside, run an inner loop to iterate through the list, merging pairs of sublists of the current `size`.
  - For each pair, split the list into `left` (of size `size`) and `right` (of size `size`).
  - Merge the `left` and `right` sublists.
  - Connect the merged sublist back into the main list.
- After the loops finish, `dummy.next` will point to the head of the fully sorted list.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { 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 t = slow . next ; slow . next = null ; ListNode l1 = SortList ( head ); ListNode l2 = SortList ( t ); ListNode dummy = new ListNode (); ListNode cur = dummy ; 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 ? l2 : l1 ; return dummy . next ; } }
```

### Java

```java
/** * 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 == 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 t = slow . next ; slow . next = null ; ListNode l1 = sortList ( head ); ListNode l2 = sortList ( t ); ListNode dummy = new ListNode (); ListNode cur = dummy ; 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 ? l2 : l1 ; return dummy . next ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var sortList =
  function (head) {
    if (!head || !head.next) {
      return head;
    }
    let slow = head;
    let fast = head.next;
    while (fast && fast.next) {
      slow = slow.next;
      fast = fast.next.next;
    }
    let t = slow.next;
    slow.next = null;
    let l1 = sortList(head);
    let l2 = sortList(t);
    const dummy = new ListNode();
    let cur = dummy;
    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 || l2;
    return dummy.next;
  };

```

### CPP

```cpp
/** * 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 ) { if ( ! head || ! head -> next ) return head ; auto * slow = head ; auto * fast = head -> next ; while ( fast && fast -> next ) { slow = slow -> next ; fast = fast -> next -> next ; } auto * t = slow -> next ; slow -> next = nullptr ; auto * l1 = sortList ( head ); auto * l2 = sortList ( t ); auto * dummy = new ListNode (); auto * cur = dummy ; 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 ; return dummy -> next ; } };
```

### Python

```python
# 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 : ListNode ) -> ListNode : if head is None or head . next is None : return head slow , fast = head , head . next while fast and fast . next : slow , fast = slow . next , fast . next . next t = slow . next slow . next = None l1 , l2 = self . sortList ( head ), self . sortList ( t ) dummy = ListNode () cur = dummy 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 # add the rest return dummy . next
```