LeetCode #148 Sort List

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #148 Sort List

문제 풀이

$O(nlog\ n)$에 연결리스트를 정렬해야 한다. $O(nlog\ n)$이니 최악의 경우 $O(n^2)$를 보이는 퀵 정렬이 아니라 병합 정렬을 사용해야 함은 자명한데 재귀 구조로 이루어진 연결리스트라서 뇌정지가 온다. 병합 정렬의 핵심은 더 이상 분할할 수 없을 때까지 2분할한 뒤 merge하는 과정이므로 우서 분할에 대해 고민해야 한다.

2분할은 런너 기법을 사용하면 되겠다. 하나의 런너가 2개씩 전진하고 이를 fast 런너라 하자. 1개씩 전진하는 런너를 slow라 하자. slow 런너는 fast 런너가 끝에 다다르면 입력받은 head의 절반을 지나쳐 우측 절반을 가르키게 된다. 그러나 좌측 절반은 아직 할당하지 못했다. 좌측 절반은 head와 할당이 똑같게끔 slow 노드를 따라가는 left 버퍼를 하나 생성하자. 전진이 종료되면 left의 다음 노드를 None으로 만들어 잘라낸다. 그렇다면 left는 head와 할당 주소가 같기 때문에 head는 slow의 시작지점 이전까지로 잘려서 좌측 절반이 완성된다.

merge 과정은 만약 두 ListNode가 존재하면 값이 작은 쪽이 l1으로 가게끔 치환하고 l1.next에 대해 재귀호출하여 한쪽 ListNode가 None이 될 때까지 호출한다. 이후 병합된 형태의 ListNode가 반환되면 재귀를 종료한다.

python 코드

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

    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        left, slow, fast = None, head, head
        while fast and fast.next:
            left, slow, fast = slow, slow.next, fast.next.next
            # left에 slow를 할당하여 slow 직전까지 따라감
        left.next = None
        # left 다음을 None으로 만들어 head의 좌측 절반까지 자름
        # 처음 slow에 head를 할당하여 서로 연결되어 있기 때문에 가능
        l1 = self.sortList(head) # 좌측 절반
        l2 = self.sortList(slow) # 우측 절반
        return self.mergeList(l1, l2)