[Leetcode] 148. Sort List (python)

#1.  문제

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

Sort List - LeetCode

 

 

주어진 연결 리스트를 정렬 상태로 반환하는 문제

 

Input: 
head = [-1, 5, 3, 4, 1]

Output: 
[-1, 1, 3, 4, 5]

Explanation:
병합정렬로 풀이

 

 

---

#2.  풀이

 

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        # Base case where recursion stops.
        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  # Cut the list in the middle. ex) -1 -> 5 / 3 -> 4 -> 1

        left = self.sortList(head=head)
        right = self.sortList(head=slow)

        return self.merge(left, right)

    def merge(self, left, right):

        if left and right:
            if left.val > right.val:
                left, right = right, left  # swap

            left.next = self.merge(left.next, right)

        return left or right

 

정렬 알고리즘 중 병합정렬 (merge sort)를 통해 풀이가 가능하다.

재귀와 연결리스트 모두 어려운 부분이라 결국 가장 좋은 풀이를 탐색했고, 풀이 과정들을 하나씩 적어가면서 이해하려고 노력했다.
풀이 자체도 쉽게 와닿지 않아 좌절을 했는데, 하나씩 과정을 풀어가며 이해하려고 하니 재귀에 대한 감각을 조금씩 익힐 수 있었다.

문제풀이과정인데 글씨가 엉망이라 거의 나만 참고 가능하다..