[Day 43] Sort List (Medium)

14th鐵人賽 leetcode algorithm

2022-10-28 22:55:18

828 瀏覽

分享至

148. Sort List

Solution 1: Merge Sort

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeSortedList(self, head1, head2):
        dummyNode = ListNode()
        ptrCurrHead = dummyNode
        while head1 and head2:
            if head1.val <= head2.val:
                ptrCurrHead.next = head1
                head1 = head1.next
            else: # head1.val > head2.val:
                ptrCurrHead.next = head2
                head2 = head2.next
            ptrCurrHead = ptrCurrHead.next
        
        # list2 is null
        while head1:
            ptrCurrHead.next = head1
            ptrCurrHead = ptrCurrHead.next
            head1 = head1.next
        # list1 is null
        while head2:
            ptrCurrHead.next = head2
            ptrCurrHead = ptrCurrHead.next
            head2 = head2.next

        return dummyNode.next
        

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        ptrFast = ptrSlow = ptrEndOfFirstHalfList = head
        while(ptrFast and ptrFast.next):
            ptrEndOfFirstHalfList = ptrSlow
            ptrSlow = ptrSlow.next            
            ptrFast = ptrFast.next.next
        
        ptrEndOfFirstHalfList.next = None
        headOfLftHalf = self.sortList(head)
        headOfRhtHalf = self.sortList(ptrSlow)
        head = self.mergeSortedList(headOfLftHalf, headOfRhtHalf)

        return head

Time Complexity: O(NLog(N))
Space Complexity: O(Log(N)) // The recursive call need stack