Sort List

문제

Given the head of a linked list, return the list after sorting it in ascending order.

풀이

• 주어진 링크드 리스트를 정렬하는 문제
• 링크드 리스트를 정렬하는 방법: 머지소트, 퀵소트
  • quick sort의 경우 정렬된 리스트가 입력값으로 들어오게 될 경우 편향된 리스트로 나뉘게 되므로 최악의 경우가 발생하게 된다.
  • 버블 정렬의 경우 O(n^2)이 소요되며 링크드 리스트의 최대 길이를 계산하는 과정이 필요

내장 sort 사용 - Solution(Runtime: 200ms)

python 내장 정렬 메서드 사용

1. 링크드 리스트에 있는 원소들을 배열에 담는다.
2. 배열을 정렬한다.
3. 정렬된 배열의 원소를 링크드 리스트의 앞부터 val 값을 갱신한다.

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    	# 링크드 리스트의 value만 담을 배열과 current node
        arr, curr = [], head

        while curr:
            arr.append(curr.val)
            curr = curr.next
        
        curr = head
        for e in sorted(arr):
            curr.val = e
            curr = curr.next
        
        return head

merge sort - Solution(Runtime: ms)

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

1. 런너 기법(slow, fast)으로 리스트를 두부분으로 분리한다.

• slow: 한칸, fast: 두칸씩 이동
• fast가 맨끝에 도착했을 때 slow는 중앙에 위치해있으므로 half는 slow의 이전 값으로 지정
• half.next = None으로 연결된 노드를 끊어줌
• 주어진 링크드 리스트는 head가 앞 부분, slow가 head인 뒷 부분으로 나누어짐

2. 재귀적으로 모든 노드를 쪼개고 merge 함수를 통해 크기를 비교해가며 이어준다.

class Solution:
    def merge(self, l1, l2):
        if l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1

            l1.next = self.merge(l1.next, l2)

        return l1 or l2

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if  not head or not 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.merge(l1, l2)