리트코드 148번 Sort List (python)

Problem

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

Solution

내 풀이 - 내장 함수 이용

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        val_list = []
        while head:
            val_list.append(head.val)
            head = head.next

        val_list.sort()

        head = ListNode()
        node = head
        for v in val_list:
            node.next = ListNode(v)
            node = node.next
        return head.next

다른 풀이 - merge sort

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)

        return l1 or l2

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not (head and head.next):
            return head
        
        # runner algorithm
        half, slow, fast = None, head, head
        while fast and fast.next:
            half, slow, fast = slow, slow.next, slow.next.next
        half.next = None
        
        # divide
        l1 = self.sortList(head)
        l2 = self.sortList(half)
        
        return self.mergeTwoLists(l1, l2)

책에 나온 병합 정렬을 이용한 풀이이다. 하지만 실행 시 RecursionError: maximum recursion depth exceeded in comparison이 발생한다.

Reference

파이선 알고리즘 인터뷰 58번