# LeetCode 148. Sort List

## Description

https://leetcode.com/problems/shuffle-the-array/

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

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: []
```

Constraints:

• The number of nodes in the list is in the range `[0, 5 * 104]`.
• `-105 <= Node.val <= 105`

## Explanation

Use merge sort and use a find middle helper function.

## Python Solution

``````# 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:

while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next

return slow

def merge(self, l1, l2):
dummy = ListNode(0)
l3 = dummy

while l1 and l2:
if l1.val <= l2.val:
l3.next = l1
l1 = l1.next
else:
l3.next = l2
l2 = l2.next

l3 = l3.next

if l1:
l3.next = l1

if l2:
l3.next = l2

return dummy.next

right = self.merge_sort(middle.next)

middle.next = None

return self.merge(left, right)
``````
• Time complexity: O(N logN).
• Space complexity: O(log N). where N is the number of nodes in the linked list. Since the problem is recursive, we need additional space to store the recursive call stack. The maximum depth of the recursion tree is log N.