문제
연결 리스트를 O(n*logn)에 정렬하라.
입력
- 4 → 2 → 1 → 3
출력
- 1 → 2 → 3 → 4
코드
병합 정렬
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 and l2:
if l1.val > l2.val:
l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
def sortList(self, head: ListNode) -> ListNode:
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
l1 = self.sortList(head)
l2 = self.sortList(slow)
return self.mergeTwoLists(l1, l2)내장함수 이용
from typing import List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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풀이
입력값 -1 → 5 → 3 → 4 → 0 연결 리스트의 병합 정렬 과정을 예로 들어 풀어보자.
먼저 병합 정렬의 분할 정복을 위해서는 중앙을 분할해야 한다. 그러나 연결 리스트는 전체 길이를 알 수 없기 때문에 런너 기법을 활용한다.
half, slow, fast = None, head, head
while fast and fast.next:
half, slow, fast = slow, slow.next, fast.next.next
half.next = None
l1 = self.sortList(head)
l2 = self.sortList(slow)half, slow, fast 3개 변수를 만들어 두고 slow는 한 칸씩, fast는 두 칸씩 앞으로 이동한다. 이렇게 하면 fast가 맨 끝에 도착했을 때 slow는 중앙에 도착해 있을 것이다. half는 slow의 바로 이전 값으로 한다. 그리고 마지막에는 half.next = None으로 half 위치를 기준으로 연결 리스트 관계를 끊어버린다. 이제 다음과 같이 head, slow를 기준을 재귀 호출을 해나가면 결국 연결 리스트는 -1, 5, 3, 4, 0 단일 아이템으로 모두 쪼개진다.
def sortList(self, head: ListNode) -> ListNode:
...
return self.mergeTwoLists(l1, l2)
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 and l2:
if l1.val > l2.val:
l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2마지막에는 최종적으로 쪼갰던 아이템을 크기 비교를 통해 정렬한뒤 다시 합쳐서 리턴한다. mergeTwoLists() 메소드는 연결 리스트를 입력값으로 받아, 길이가 얼마나 되든 재귀 호출을 통해 l1의 포인터를 이동하면서 정렬해 리턴한다. 여기서 return l1 or l2는 l1에 값이 있다면 항상 l1을 리턴하고, l1이 None일 경우 l2를 리턴한다.
함수들이 호출되는 과정은 다음 그림과 같다. 이해가 될지 모르겠지만…ㅠㅡㅠ
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]