[알고리즘/python] LeetCode 148. Sort List

📑 1. 문제 이해

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

Sort List - LeetCode

💡 2. 알고리즘 설계

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def sort(head: Optional[ListNode], total: int):
            # print("head", head.val, "size", total)
            if not head or not head.next:
                return head
            left = head
            left_size = 1

            curr = head
            for _ in range(total // 2 - 1):
                curr = curr.next
                left_size += 1
            right = curr.next
            right_size = total - left_size

            curr.next = None

            # print("left", makeList(left), "right", makeList(right))
            sorted_left = sort(left, left_size)
            sorted_right = sort(right, right_size)
            # 병합 정렬?
            print(makeList(sorted_left), makeList(sorted_right))

            if not sorted_left:
                return sorted_right
            if not sorted_right:
                return sorted_left

            if sorted_left.val > sorted_right.val:
                sortedHead = sorted_right
                sorted_right = sorted_right.next
            else:
                sortedHead = sorted_left
                sorted_left = sorted_left.next

            prev = sortedHead

            while sorted_left and sorted_right:
                if sorted_left.val > sorted_right.val:
                    prev.next = sorted_right
                    prev = sorted_right
                    sorted_right = sorted_right.next
                else:
                    prev.next = sorted_left
                    prev = sorted_left
                    sorted_left = sorted_left.next

            if sorted_left:
                prev.next = sorted_left

            if sorted_right:
                prev.next = sorted_right
            print("sorted", makeList(sortedHead))
            return sortedHead

        count = 0
        curr = head
        while curr:
            count += 1
            curr = curr.next

        return sort(head, count)