[코테] 리트코드 파이썬 148번 Sort List, 머지소트(Merge sort)

Sort List - LeetCode

 

Node로 연결된 linked list를 정렬하는 문제이다.

 

첫 시도에는 정렬된 최종리스트를 저장한 노드의 head를 선언해 value와 next node를 지정해주었다. 이후 주어진 linked list를 처음부터 끝 노드까지 읽으며 최종리스트의 해당되는 위치에 넣어주는 로직을 생각했다.

해당 로직의 수행을 위해 최종리스트 전체를 읽으며 값을 확인하고, 읽고 있는 노드가 들어가야할 적합한 위치에 넣어주고자 하였다. 하지만 계속해서 최종리스트를 읽어야 할 때의 비용과 head를 저장할 방법을 찾지 못해 실패하였다.

class Solution3: 
    def sortList3(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if (not head):
            return head

        # 정렬된 최종리스트를 저장할 노드의 head
        one=ListNode()
        one.value=head
        one.next=head.next
        head=head.next
        
        # 해당 함수에서 one 노드 전체를 읽으며 val을 확인하여 head1의 위치를 찾고자 하였다
        # head를 저장할 방법의 부재로 실패
        def check(one1,head1):
            if one1.val < head1.val:
                head1.next=one1.next
                one1.next=head1
            else:
                one1=one1.next
                check(one1,head1)

        # linked list를 처음부터 끝 노드까지 읽어서 함수를 호출한다
        while head:
            check(one,head)
            head=head.next

        return one

 

최종코드는 머지소트로 구현한 코드이다. 더미 노드를 만들어 head를 가리키게 한 뒤, 리턴값으로 더미 노드의 다음 노드를 반환하는 전략이다.

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # node개수가 0이거나 1일때 return
        if not head or not head.next:
            return head

        # linked 리스트의 mid를 찾기 위해 두 개의 리스트로 나눈다.(slow, fast)
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 이를 통해 slow의 next 노드가 중간 노드가 된다.
        mid = slow.next
        # linked 리스트의 왼편과 오른편을 나누기 위해 slow.next를 null로 두기
        slow.next = None

        # 왼쪽과 오른쪽 노드들을 재귀적으로 계산해서 정렬
        left = self.sortList(head)
        right = self.sortList(mid)

        # 정렬된 두 리스트를 합치기 (merge sort)
        dummy = ListNode(0)
        curr = dummy
        while left and right:
            if left.val < right.val:
                curr.next = left
                left = left.next
            else:
                curr.next = right
                right = right.next
            curr = curr.next
        # 왼쪽이나 오른쪽 리스트에 남아있는 것을 최종 리스트의 마지막에 붙이기
        curr.next = left or right

        # dummy의 next 노드가 정렬된 최종 리스트의 head가 된다
        return dummy.next