# 0148. Sort List

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Sort List](https://leetcode.com/problems/sort-list/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0148-sort-list)

Given the `head` of a linked list, return *the list after sorting it in **ascending order***.

**Follow up:** Can you sort the linked list in `O(n logn)` time and `O(1)` memory (i.e. constant space)?
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of nodes in the list is in the range `[0, 5 * 10^4]`.
* `-10^5 <= Node.val <= 10^5`

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

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

Input: head = []
Output: []
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
To meet O(1) memory complexity, we need to do **Merge Sort** by **splitting** the linked list into multiple segments **bottom-up**.
{% endhint %}

Before splitting, we need to **get the length** of the input linked list.

Then split the linked list bottom-up by starting with **`size = 1`**, this size will grow two times of itself in each iteration by **`size *= 2`** until `size >= length`.

For the process of **splitting and merging**, we need to maintain two pointers:

1. **splitHead** is to check *whether the splitting process needs to end* or not.
2. **mergeHead** is for merging two split linked lists so that we can *maintain relative order for the next splitting process*.
   {% endtab %}
   {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        #  (base case)
        if not head or not head.next: return head
        
        # ==================================================
        #  Linked List + Merge Sort           (Iterative)  =
        # ==================================================
        # time  : O(nlog(n))
        # space : O(1)
        
        length = self.getSize(head)
        ret, size = ListNode(0, head), 1
        
        while size < length:
            splitHead, mergeHead = ret.next, ret
            
            while splitHead:
                left  = splitHead
                right = self.split(size, left)
                
                splitHead = self.split(size, right)
                mergeHead = self.merge(left, right, mergeHead)
            
            size *= 2
        
        return ret.next
        
    def getSize(self, node: ListNode) -> int:
        size, tmp = 0, node
        while tmp: size, tmp = size + 1, tmp.next
        return size
    
    def split(self, size: int, node: ListNode) -> ListNode:
        pre = None
        for i in range(size):
            if not node: break
            pre, node = node, node.next
        
        #  (break the link)
        if pre: pre.next = None
        return node
    
    def merge(self, left: ListNode, right: ListNode, head: ListNode) -> ListNode:
        while left and right:
            if left.val <= right.val: head.next, left = left, left.next
            else: head.next, right = right, right.next
                
            head = head.next
        
        head.next = left if left else right
        while head.next: head = head.next
        return head
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(nlog(n))
     * @space : O(1)
     */
    
    public ListNode sortList(ListNode head) {
        /* base case */
        if(head == null || head.next == null) return head;
        
        int len = getLen(head);
        
        int size = 1;
        ListNode ret = new ListNode(0, head);
        
        while(size < len) {
            ListNode splitHead = ret.next, mergeHead = ret;
            while(splitHead != null) {
                ListNode left  = splitHead;
                ListNode right = split(size, left);
                
                splitHead = split(size, right);
                mergeHead = merge(left, right, mergeHead);
            }
            
            size *= 2;
        }
        
        return ret.next;
    }
    
    public int getLen(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while(cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }
    
    public ListNode split(int size, ListNode node) {
        ListNode pre = null;
        for(int i=0 ; i<size ; i++) {
            if(node == null) break; 
            pre = node;
            node = node.next;
        }
        /* break the link */
        if(pre != null) pre.next = null;
        return node;
    }
    
    public ListNode merge(ListNode left, ListNode right, ListNode head) {
        while(left != null && right != null) {
            if(left.val <= right.val) {
                head.next = left;
                left = left.next;
            } else {
                head.next = right;
                right = right.next;
            }
            head = head.next;
        }
        head.next = (left != null) ? left : right;
        while(head.next != null) head = head.next;
        return head;
    }
}
```

{% endtab %}
{% endtabs %}