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 slowAs 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 resultWe 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 resultThe 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.
