Sort List

Patrick Leaton
Published: June 9, 2021, 7:55 p.m.
Problem Description

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 * 10^4].
  • -10^5 <= Node.val <= 10^5

 

The description was taken from https://leetcode.com/problems/sort-list/.

Problem Solution

#O(N(Log N)) Time, O(Log N) Space
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        mid = self.get_mid(head)
        left = self.sortList(head)
        right = self.sortList(mid)
        return self.merge(left,right)
       
    def get_mid(self, head: ListNode) -> ListNode:
        slow=fast=head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        return mid
   
    def merge(self, left: ListNode, right:ListNode) -> ListNode:
        dummy = ListNode(0)
        merger = dummy
        while left and right:
            if left.val < right.val:
                merger.next = left
                left = left.next
            else:
                merger.next = right
                right = right.next          
            merger = merger.next
        merger.next = left or right
        return dummy.next

Problem Explanation

If we're given a linked list and asked to sort it like in this problem and Merge K Sorted Lists, a Merge Sort is going to be a good option because we can recursively break down the list(s) into lists of single nodes, then sort and merge each of these nodes individually.

This is going to come down to a couple of steps:

  1. Break the list into single nodes by recursively getting the middle node of the given partition and breaking the list from that point.

  2. Once broken, sort and merge the two halves of the just broken partition within a Depth-First Search manner where the sorted partitions grow as the call stack becomes empty.

Since we are having to implement this algorithm on a linked list instead of an array, it makes it slightly more difficult.  

To start, we will create a couple of helper functions.

The first will be get_mid that will tell us which node of our current list is the middle node so that we can cut the list in half at this point.

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

 

Since we don't have an array, we can't just return the middle node in constant time.

To get the middle node in a single pass we will use Floyd's Tortoise and Hare algorithm.

This works by having two pointers, fast and slow, initially at the head of the linked list.

        slow=fast=head

 

We will use a loop to traverse the current list.

The loop will run until the fast pointer is either at or behind the tail of the list.

        while fast.next and fast.next.next:

The reason why we want to stop if the fast pointer is two nodes away from a None value is that we are incrementing the pointer by two nodes each time.

While in the loop, we will increment the slow pointer by one node and the fast pointer by two.

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

 

Once we are out of the loop, that means the fast pointer is at or behind the tail, so the mid node would be the node one place after the slow pointer.

1->2->3->4->5->None

If the function had the input of [1,2,3,4,5] shown above, the fast pointer would break when it was two places away from the None value, one node from the tail.  The slow pointer would be one node behind the mid node, three.

        mid = slow.next

Once we know where the mid node is, we will break the current list into two lists.  

The mid node will be the head of the second list.

1->2->None   3->4->5->None 

        slow.next = None

All there is left to do now is to return the mid node, three, which is the head of the right list.

        return mid

We will also need a merge function.  This is the same function used in the solution of Merge Two Sorted Lists.

This function will take a left and right sublist, initially a single node since that is the size we broke the problem's initial list into, and it will use a pointer to sort the nodes in ascending order before returning a sorted sublist.  That sublist will be compared against other sublists returned from this function in the future and that is how the overall linked list will be sorted.

    def merge(self, left: ListNode, right:ListNode) -> ListNode:

We will start by creating a dummy node and a merger pointer.  

The dummy node is created so that we don't have to handle the initial logic of seeing which node should go first in the list.

        dummy = ListNode(0)
        merger = dummy

 

Next, we will have loop that will run while the current node in both sublists aren't None.

        while left and right:

In each iteration, we will compare the two values.  

If the left node is less than the right node, we will merge the left node into the output list and increment the left pointer.

            if left.val < right.val:
                merger.next = left
                left = left.next

 

Otherwise, we will do the same thing but for the right node.

            else:
                merger.next = right
                right = right.next    

 

After we have merged the lesser node into the output list, we will increment the merger pointer.

            merger = merger.next

Once we have broken from the loop, it means that at least one node is None so we will just merge whichever node isn't None into the output list and return it with the node after the dummy node being the head.

        merger.next = left or right
        return dummy.next

Now we can hop back to our main recursive function, sortList.

Since this function is recursive, we need to make sure we make our base case first, or else this function will run indefinitely.

Our goal is to cast a Depth First Search fishing hook down to break the input list into single nodes, then to have those nodes be sorted in the deepest depth of the recursive pond, begin emerging and join together while still sorting, then pop up into our boat as a glorious fifty pound sorted linked list that we can show off in a picture at the bar while wearing a flannel cut-off.

In other words, at the bottom of our recursive tree, we are only going to want a single tail node.  If the node is pointing to None, our function will return the node.  If the node is None, our function will return None.

        if not head or not head.next:
            return head

 

We will get the mid node which if we recall, will be the head of the right list.  We will then recurse the left and right sublists until the base case is met at the bottom of the recursive tree, and then we will merge the sublists to climb back up the recursive tree with our initial recursive call returning the final, sorted linked list.

        right = self.sortList(mid)
        return self.merge(left,right)