# 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