[Leetcode] 148. Sort List

https://leetcode.com/problems/sort-list/description/?envType=study-plan-v2&envId=top-interview-150

initial

coming for merge sort https://velog.io/@whitehousechef/Merge-sort I tried using the same template but i made severl mistakes

1) need to check that for merge function, if its either not head or not head.next cuz in merge sort the check is if len(lst)<=1. There can be no node as the end recursion condition
2) V impt, in the merge_sort function, u need to Keep track of the head of your new merged list (which is what head does)
Keep track of where to attach the next node (which is what current does)

solution

# 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 find_mid(given_node):
            slow=given_node
            fast=given_node
            while fast.next and fast.next.next:
                slow=slow.next
                fast=fast.next.next
            return slow
        def merge(node):
            if not node or not node.next:
                return node

            hola=find_mid(node)
            tmp = hola.next
            hola.next=None
            left = merge(node)
            right=merge(tmp)
            return merge_sort(left,right)
        def merge_sort(left_start,right_start):
            head = ListNode(0)
            current = head
            while left_start and right_start:
                if left_start.val<right_start.val:
                    current.next=left_start
                    left_start=left_start.next
                else:
                    current.next=right_start
                    right_start=right_start.next
                current=current.next
            if left_start:
                current.next=left_start
            if right_start:
                current.next=right_start
            return head.next
        return merge(head)
        
        

complexity

n log n time
1 space