148. Sort List

148. Sort List

這題的想法是 Merge Sort (Accepted) ，Merge Sort 的核心是不斷的將一串數列從「中間分一半」： 876. Middle of the Linked List ，再從小的問題慢慢的合併起來： 21. Merge Two Sorted Lists

比較特別的一點是因為這是一個 Linked List ，所以這題有一個地方要注意，那就是比較慢的那個點，其實是要先找到「中間點」的前一個點，因為當要做 Divide 時，我們要從中間切開，因此我們先記錄好中間點後，要從中間點的前一個點，把 Linked List 從「中間點」斷開，斷開後在後面的 Merge List 裡面合併起來。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast, slow = head.next, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        mid = slow.next
        slow.next = None
        return mid

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        prevHead = ListNode(-1)
        prev = prevHead
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next
            prev = prev.next

        prev.next = l1 if l1 else l2
        return prevHead.next

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        mid = self.middleNode(head)
        left = self.sortList(head)
        right = self.sortList(mid)
        return self.mergeTwoLists(left, right)