[Leetcode/파이썬] 148. Sort List

Sort List

---

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

 

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

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

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is in the range [0, 5 * 104].
• -105 <= Node.val <= 105

 

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None :
            return head


        slow, fast = head, head.next

        while fast and fast.next :
            slow = slow.next
            fast = fast.next.next

        mid = slow.next
        slow.next = None 

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

        return self.merge(left, right)

    def merge(self, l1, l2) :
        dummy = ListNode(-10001)
        curr = dummy

        while l1 and l2 :
            if l1.val < l2.val :
                curr.next = l1
                l1 = l1.next

            else :
                curr.next = l2
                l2 = l2.next

            curr = curr.next

        curr.next = l1 or l2

        return dummy.next

이 문제는 무슨 문제인지 몰랐는데, 마지막에 $O(N log N)$ 을 보고 분할 정복을 활용하면 되겠다고 생각했다. 분할 정복을 활용한 정렬방법은 병합 또는 합병 정렬 (Merge Sort)를 선택하였다. 아니 선택만 하였다. 

여기서 문제는 

1. 병합 정렬은 절반씩 더 이상 나눌 수 없을 때까지 나누고 비교하면서 합치는 과정을 거치는 건데, mid를 구하는 방법.
2. 합치는 걸 어떻게 구현하지? 

절반 찾기, 그리고 합치기를 생각해보자. => 결국 못함...

처음 가지를 쳤다 => head가 None이거나 head가 하나일 때는 의미가 없으므로 return head

mid를 찾아보자. 한 번에 두 칸씩 움직이는 fast, 한 칸씩 움직이는 slow를 두고 fast가 끝까지 움직일 때 까지 움직인다. 그러면 slow는 fast보다 절반 느리기 때문에 while 문이 끝나게 되면 slow는 mid가 된다. => mid 찾기 성공

그럼 병합 정렬은 나눌 수 없을 때 까지 나누는 거니까 이를 재귀함수로 구현하면 된다. left 는 head = index 0, right는 mid = index는 아마 1이 될 때 까지 하게 될 것이다. 아 이때 이 값은 가장 처음 가지치기 라고 생각했던 if 문에 걸리게 되네? 

4, 2 를 비교 => [2, 4]

1, 3 비교 => [1, 3]

[2, 4] [1, 3] 비교 => [1, 2, 3, 4]

만약 length 가 홀 수면 남은 수를 하나 넣게 된다. 

봐도봐도 이해가 잘 안되는 코드다. if head is None or head.next is None : return head 부분만 얻어 걸리고 나머지는 다 참고한 코드이다. 이렇게도 풀 수 있는 문제라는게 참 재밌었다.