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

**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`

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.

`def get_middle_linkedlist(self, head):`

slow = head

fast = head

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

if head == None or head.next == None:

return head

mid = self.get_middle_linkedlist(head)

next_mid = mid.next

mid.next = None

left = self.sortList(head)

right = self.sortList(next_mid)

result = self.sorted_head(left, right)

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.

`def sorted_head(self, left, right):`

if left == None:

return right

if right == None:

return left

if(left.val <= right.val):

result = left

result.next = self.sorted_head(left.next, right)

else:

result = right

result.next = self.sorted_head(left, right.next)

return result

The complete code is as follows.

class ListSorter:

def sorted_head(self, left, right):

if left == None:

return right

if right == None:

return left

if(left.val <= right.val):

result = left

result.next = self.sorted_head(left.next, right)

else:

result = right

result.next = self.sorted_head(left, right.next)

return result

def get_middle_linkedlist(self, head):

slow = head

fast = head

while(fast.next and fast.next.next):

slow = slow.next

fast = fast.next.next

return slow #start

def sortList(self, head: ListNode) -> ListNode:

if head == None or head.next == None:

return head

mid = self.get_middle_linkedlist(head)

next_mid = mid.next

mid.next = None

left = self.sortList(head)

right = self.sortList(next_mid)

result = self.sorted_head(left, right)

return result

**Time Complexity**

We are dividing our linked list into halves at the divide phase. The time complexity for the divide phase is O(logn) since the division of the LinkedList occurs parallelly. During the merge phase, we go through each node in the LinkedList, which has a time complexity of O(n). Therefore in total, the time complexity is O(nlogn).

**Space Complexity**

We are using recursion to perform merge-sort and we are traversing through all the nodes. Since recursion uses stack internally, the space complexity is O(n).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.