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

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

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

출처 : 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를 이전에 봤었는데 또 까먹었다! 기억하자

from http://pythaac.tistory.com/143 by ccl(A) rewrite - 2021-08-07 00:00:15