Problem statement

https://binarysearch.com/problems/Sort-a-Linked-List/

Solution

Equal to Leetcode 0148. Sort List.

Complexity

It is O(n log n) for time and O(log n) for space.

Code

class Solution:
    def solve(self, head):
        if not head or not head.next: return head
        mid = self.getMid(head)
        left = self.solve(head)
        right = self.solve(mid)
        return self.merge(left, right)
    
    def getMid(self, head):
        slow, fast = head, 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, head1, head2):
        dummy = tail = LLNode(None)
        while head1 and head2:
            if head1.val < head2.val:
                tail.next, tail, head1 = head1, head1, head1.next
            else:
                tail.next, tail, head2 = head2, head2, head2.next
    
        tail.next = head1 or head2
        return dummy.next