[파이썬 알고리즘 인터뷰][정렬] 리스트 정렬

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

연결 리스트 정렬

 

책에서 구현된 코드

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

 

기억해야할 기법

• 연결 리스트 정렬 방법 
  
  • 연결 리스트를 순차탐색하여 비교할값들의 배열로 바꿈
  • 정렬
  • 연결 리스트를 순차탐색하여 정렬된 값으로 바꿈
• Runner
  • 연결 리스트에서 길이를 모를 때, 중간 위치를 찾는 방법
  • slow는 1칸, fast는 2칸씩 다음 포인터로 이동
  • fast가 끝에 도달하면 slow의 위치가 중간

 

내가 구현한 코드

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        root = head
        if root:
            arr = [root]
            while root.next:
                arr.append(root.next)
                root = root.next
            arr.sort(key=lambda x : x.val)

            for i in range(len(arr)-1):
                arr[i].next = arr[i+1]
            arr[-1].next = None
            root = arr[0]

        return root

• 책에서 구현한 알고리즘이 더 빠르다
• 나는 노드를 배열로 만들고, 노드의 값으로 정렬해서, 배열 순서대로 노드를 다시 연결했다
• 이 노드에는 포함된 데이터가 하나(val)이므로 책에서 구현한 알고리즘이 더 효율적이다
• 그리고 Runner를 이전에 봤었는데 또 까먹었다! 기억하자