148. Sort List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # time O(NlgN)  space O(lgN)

    # step1 merge sort: 1. get middle 2.get left list 3. get right list 4. merge left and right list 
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        mid = self.getMid(head)
        l = self.sortList(head)
        r = self.sortList(mid)
        return self.merge(l,r)
    
    # step2,find middle of list and cut from middle into two smaller lists 
    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 
    # step3: create a dummy node and a pointer, (assuming li1 and li2 not empty)keep comparing list 1 and list2 make sure pointer get local smallest;  after one of the lists reached the end, attach the rest of the other list to the pointer and exit the merge sort . 
    def merge(self,h1,h2):
        dummy = p = ListNode(0)
        while h1 and h2:
            if h1.val < h2.val:
                p.next = h1
                h1 = h1.next
                #p.next,p,h1 = h1,h1,h1.next
            else:
                p.next = h2
                h2  = h2.next
            p = p.next
                #p.next,p,h2 = h2,h2,h2.next
            # attach rest of either list which hasn't reached the end
            p.next = h1 or h2
        return dummy.next