58. Sort List

🎯 leetcode - 148. Sort List

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 58번 문제

💡 Code

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

📌 날짜

2020.02.26

📌 시도 횟수

5 try

💡 문제 해결 방법

- 사실 내 머리로는 연결리스트를 파이썬 리스트로 변경한 후 list.sort()를 
사용해서 정렬하고 다시 리스트를 연결리스트로 옮기는 방법만 생각이 났다😢
- 좀더 문제의 의도에 맞는 방법으로 풀 수는 없을까? 생각했다.

💡 새롭게 알게 된 점

- 근데 사실 이 방법이 제일 빠르다.ㅋㅋ😂

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 

---

😉 다른 풀이

📌 하나. 병합 정렬 이용하기

class Solution:
    # 2개의 linked list를 순서대로 합치기
    def merge(self, l1, l2):
        if not l1 or not l2:
            return l1 or l2

        head = dummy = ListNode(0)

        while l1 and l2:
            if l1.val <= l2.val:
                head.next = l1
                l1 = l1.next
            else:
                head.next = l2
                l2 = l2.next
            head = head.next
        head.next = l1 or l2
        return dummy.next

    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        # 런너 기법을 사용해서 연결리스트를 분할하기
        half, slow, fast = None, head, head
        while fast and fast.next:
            half = slow
            slow = slow.next
            fast = fast.next.next
        half.next = None

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

        return self.merge(l1, l2)

💡 문제 해결 방법

• 문제 해결 과정은 아래와 같다.
  

1. 런너 기법을 활용하여 연결리스트를 이등분한다. (더이상 안쪼개질때까지, 재귀 사용)
2. 더이상 쪼개지지 않으면 merge 함수로 정렬하면서 합친다.
3. 재귀로 처리했던 부분을 리턴하면서 정렬된 연결리스트를 만들어간다.
(정렬된 연결리스트를 리턴해서 l1, l2로 받고 다시 l1, l2를 하나의 정렬된 리스트로 만들기를 반복)
4. 최종적으로는 merge 함수의 dummy.next 가 반환되어 정렬된 하나의 연결리스트의
루트가 리턴된다.

💡 새롭게 알게 된 점

⭐ merge(l1, l2) 이해하기 ⭐
(*재귀보다 반복문이 더 직관적이고 이해가 잘돼서 반복문으로 풂)
0. l1, l2는 이미 정렬된 연결 리스트이다.
1. l1, l2 둘 다 존재하는 경우 더 큰 값을 head.next에 연결하고,
연결한 노드만 next로 이동시킨다.
2. 만약 l1 또는 l2 둘 중 한개가 먼저 마지막 노드까지 도달해버렸다면
그 뒤는 자동적으로 나머지 연결리스트의 남은 부분이 연결된다.
즉, head.next = l1 or l2
3. return dummy.next

⭐ 런너 기법 이해하기 ⭐
- 보통 2개의 런너를 사용한다. 빠른 런너(fast runner)와 느린 런너(slow runner)
- 대개 빠른 런너는 두 칸씩 건너 뛰고, 느린 런너는 한 칸씩 이동하게 된다.
- 빠른 런너가 연결 리스트의 끝에 도달하면, 
느린 런너는 정확히 연결 리스트의 중간 지점을 가리키게 된다.

🎈참고 : 런너 기법에 대한 설명 보기(13번 문제)