Sort List – Solution & Complexity

def sort_list(head: ListNode) -> ListNode:
    values = []
    current = head
    while current is not None:
        values.append(current.val)
        current = current.next

    values.sort()

    dummy = ListNode()
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next

    return dummy.next

def sort_list(head: ListNode) -> ListNode:
    if head is None or head.next is None:
        return head

    slow = head
    fast = head.next
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    right_head = slow.next
    slow.next = None

    left_sorted = sort_list(head)
    right_sorted = sort_list(right_head)

    dummy = ListNode()
    tail = dummy

    while left_sorted is not None and right_sorted is not None:
        if left_sorted.val <= right_sorted.val:
            tail.next = left_sorted
            left_sorted = left_sorted.next
        else:
            tail.next = right_sorted
            right_sorted = right_sorted.next
        tail = tail.next

    tail.next = left_sorted if left_sorted is not None else right_sorted
    return dummy.next