Image for post
Image for post
Photo by JJ Ying on Unsplash

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:

Image for post
Image for post

Example 2:

Image for post
Image for post

Example 3:

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.

Image for post
Image for post
Dividing array to subarray
Image for post
Image for post
Merging sorted subarray

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.

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.

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.

The complete code is as follows.

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.

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store