Challenge

Given a linked list, your task is to sort it in ascending order.

Solution 1 - TLE

Using a bubble sort approach.

class Solution:
    
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        not_sorted = True
        if not head:
            return
        while not_sorted:
            tmp = head
            not_sorted = False
            while tmp.next:
                if tmp.val > tmp.next.val:
                    tmp.val, tmp.next.val  = tmp.next.val, tmp.val
                    not_sorted = True
                tmp = tmp.next
        return head

Time Complexity: O(n^2)

Solution 2

Using a merge sort approach sort approach.

class Solution:

    def get_len(self, head):
        tmp = head
        l = 0
        while tmp:
            l += 1
            tmp = tmp.next
        return l

    def merge_sort(self, head):
        lenn = self.get_len(head)
        if lenn < 2:
            return head
        mid = lenn // 2
        l = head
        i = 0
        while i < mid-1:
            l = l.next
            i += 1
        r = l.next
        l.next = None
        left = self.merge_sort(head)
        right = self.merge_sort(r)
        return self.merge(left, right)

    def print_list(self, head):
        tmp = head
        while tmp:
            print("val:", tmp.val)
            tmp = tmp.next

    def merge(self, left, right):
        head = ListNode()
        tmp = head
        while left and right:
            if left.val > right.val:
                tmp.next = ListNode(right.val)
                right = right.next
                tmp = tmp.next
            else:
                tmp.next = ListNode(left.val)
                left = left.next
                tmp = tmp.next
        while left:
            tmp.next = ListNode(left.val)
            left = left.next
            tmp = tmp.next
        while right:
            tmp.next = ListNode(right.val)
            right = right.next
            tmp = tmp.next
        return head.next

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.merge_sort(head)

Time complexity: O(n*log n)