Problem of The Day: Sort List

Problem Statement

Intuition

When tackling this problem, my initial thoughts revolve around the concept of merge sort, which is efficient for sorting linked lists. The idea is to recursively divide the list into smaller sublists until each sublist contains only one element, and then merge these sublists while ensuring the elements are in ascending order.

Approach

To implement this approach, I’ll define a function to split the list into two halves, find the middle node using the slow and fast pointer technique. Then, I’ll recursively sort the two halves and merge them back together in sorted order.

Complexity

• Time complexity: O(n logn )

• Space complexity: O(n)

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def getMiddleNode(head_node):
            slow = fast = head_node
            prev = None
            while fast and fast.next:
                prev = slow
                slow = slow.next
                fast = fast.next.next
            return prev, slow

        def merge(l1, l2):
            dummy = ListNode(0)
            curr = dummy
            while l1 and l2:
                if l1.val < l2.val:
                    curr.next = l1
                    l1 = l1.next
                else:
                    curr.next = l2
                    l2 = l2.next
                curr = curr.next

            curr.next = l1 if l1 is not None else l2
            return dummy.next


        def helper(node):
            if not node:
                return
            if node and not node.next:
                return node
            l1_head = node
            prev, l2_head = getMiddleNode(node)
            if prev:
                prev.next = None
            left_node = helper(l1_head)
            right_node = helper(l2_head)
            return merge(left_node, right_node)


        return helper(head)

For following up questions - EDITORIAL SOLUTION

O(1) space complexity

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        n = self.getCount(head)
        start = head
        dummyHead = ListNode()
        size = 1
        while size < n:
            self.tail = dummyHead
            while start is not None:
                if start.next is None:
                    self.tail.next = start
                    break
                mid = self.split(start, size)
                self.merge(start, mid)
                start = self.nextSubList
            start = dummyHead.next
            size *= 2
        return dummyHead.next

    def split(self, start, size):
        midPrev = start
        end = start.next
        # Use fast and slow approach to find middle and end of second linked list
        for index in range(1, size):
            if end and end.next:
                end = end.next.next
            else:
                if end:
                    end = end.next
            if midPrev.next:
                midPrev = midPrev.next
        mid = midPrev.next
        midPrev.next = None
        self.nextSubList = end.next if end else None
        if end:
            end.next = None
        # Return the start of second linked list
        return mid

    def merge(self, list1, list2):
        dummyHead = ListNode()
        newTail = dummyHead
        while list1 and list2:
            if list1.val < list2.val:
                newTail.next = list1
                list1 = list1.next
            else:
                newTail.next = list2
                list2 = list2.next
            newTail = newTail.next
        newTail.next = list1 if list1 else list2
        # Traverse till the end of merged list to get the newTail
        while newTail.next:
            newTail = newTail.next
        # Link the old tail with the head of merged list
        self.tail.next = dummyHead.next
        # Update the old tail to the new tail of merged list
        self.tail = newTail

    def getCount(self, head):
        cnt = 0
        ptr = head
        while ptr:
            ptr = ptr.next
            cnt += 1
        return cnt