정렬_1. Sort List

leetcode 148. Sort List

문제

연결 리스트를 O(n log n)에 정렬하라.

입출력예시

• 입력: 4, 2, 1, 3
• 출력: 1, 2, 3, 4

풀이

다양한 정렬 방식을 이용할 수 있는 문제로, O(n log n)의 시간 복잡도 제약 때문에 버블 정렬은 사용할 수 없다. 따라서 병합 정렬과 내장 함수를 이용한 방법으로 풀이가 가능하다.

병합 정렬

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: ListNode) -> ListNode:
        if not (head and head.next):
            return head

        half, slow, fast = None, head, head
        while fast and fast.next:
            half, slow, fast = slow, slow.next, fast.next.next
        half.next = None

        l1 = self.sortList(head)
        l2 = self.sortList(slow)

        return self.mergeTwoLists(l1, l2)

• runtime: 572 ms
• memory: 50.9 MB

팀 정렬

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

        lst.sort()

        p = head
        for i in range(len(lst)):
            p.val = lst[i]
            p = p.next
        return head

• runtime: 160 ms
• memory: 30.1 MB

파이썬 내장함수인 sort()를 사용하면 직접 병합 정렬을 구현하는 것 보다 실제로 빠르게 정렬되는 것을 볼 수 있다.

참고
파이썬 알고리즘 인터뷰