# Sort List — Day 17(Python)

--

Today we will be visiting one of the questions from Leetcode’s daily coding challenge October edition.

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

Example 1:

Output: [1,2,3,4]

Example 2:

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

Example 3:

Output: []

Constraints:

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

To sort LinkedList, we usually use merge-sort. To understand why merge-sort, we need to understand the working of merge-sort.
Merge-sort, as the name suggests, is one of the sorting algorithms. It falls in the Divide and Conquer category of algorithms. The basic idea is to divide a given array into subarrays until such that just one element is present in the subarray. After division, we compare each subarray and merge them. Eventually, we get a sorted array as our output.

The below image depicts the division array to subarrays of size 1.

In the above example, I have used an array to perform merge-sort. Additionally, we can have LinkedList to perform merge-sort. If we notice, we are dividing our list in the middle. How do we find the middle of the LinkedList?
One of the ways to find mid of the LinkedList is using two pointers. One of the pointers is slow, while the other pointer is fast. The fast one will traverse the LinkedList at twice the speed, hence the name fast pointer.

while(fast.next and fast.next.next):
slow = slow.next
fast = fast.next.next
return slow

As we are traversing through the entire list, the time complexity for the above code snippet is O(N). We are not storing any data during the calculation of mid, except for pointers. Hence the space complexity is O(1).

Since we know how to calculate the middle of the LinkedList, let us see the code snippet for dividing the LinkedList.

def sortList(self, head: ListNode) -> ListNode:
next_mid = mid.next
mid.next = None
right = self.sortList(next_mid)

return result

We have used recursion to divide the LinkedList. The base condition in our case is when we have no head node or if the node is a single node. Find the mid of the LinkedList using the function get_middle_linkedlist() defined earlier. Keep track of the node next to the middle node. After finding the middle, detach the middle node from its next node, helping in forming separated nodes.

Once we get separated nodes, compare each node’s value with each other, and place them in order. At times, the left/right node can be none, return the other node in those cases.

if left == None:
return right
if right == None:
return left
if(left.val <= right.val):
result = left
else:
result = right
return result

The complete code is as follows.

class ListSorter:

if left == None:
return right
if right == None:
return left
if(left.val <= right.val):
result = left
else:
result = right
return result

while(fast.next and fast.next.next):
slow = slow.next
fast = fast.next.next
return slow
#start
def sortList(self, head: ListNode) -> ListNode:
next_mid = mid.next
mid.next = None
right = self.sortList(next_mid)