[LeetCode] 148. Sort List

Problem : https://leetcode.com/problems/sort-list/

Use merge sort to get O( n log n ) time complexity.

# 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: ListNode) -> ListNode:
        if not head or not head.next:
            return head
              
        # divide into 2 parts
        fast, slow = head, head
        
        while fast and fast.next:
            fast = fast.next.next
            if fast:
                slow = slow.next
            
        tmp = slow.next
        slow.next = None

        left = self.sortList(head)
        right = self.sortList(tmp)

        return self.merge(left, right)
    
    def merge(self, left, right):
        dummy = ListNode(0)
        p = dummy
        
        while left and right:
            if left.val <= right.val:
                p.next = left
                p = p.next
                left = left.next
            else:
                p.next = right
                p = p.next
                right = right.next
        
        while left:
            p.next = left
            p = p.next
            left = left.next
        
        while right:
            p.next = right
            p = p.next
            right = right.next
        
        p.next = None
        
        return dummy.next