문제링크: https://leetcode.com/problems/insertion-sort-list/
요즘 포스팅을 잘 하지 못했는데, 핑계대기는 좀 그렇다. 걍 게을러서 안한거지 뭐ㅎㅎㅎ쓰는데 뭐 얼마나 걸린다고.
오늘은 지금까지의 문제와는 조금 생소한 문제이다. 삽입 정렬인데, 나도 학부때 몇번 보고는 이번에 처음 보는것 같다.
이 문제가 삽입정렬의 기초를 보기 가장 좋은 문제같아서 들고와 보았다.
Problem
문제는 아주 간단하다. 삽입정렬을 이용해서, linked list를 정렬하면 되는것이다.
Approach & Solution
일단 삽입정렬에 대해서 조금 살펴보고 들어가자
Insertion Sort
GeeksforGeeks: https://www.geeksforgeeks.org/insertion-sort/
삽입 정렬: https://www.daleseo.com/sort-insertion/
두 링크에 아주 자세하게 잘 설명되어있다. 내가 여기에 주저리는것보단, 저 링크를 읽는게 더 유익 할것 같아서 따로 설명을 하고 싶지는 않다.
요약을 해보자면, 구현이 간단하긴 하지만 시간복잡도가 O(N^2)이다보니 병합 정렬이나, 팀 소트에 밀린 감이 있다.
그럼에도 작은 세트의 데이터에는 아주 효과적이며, 정말 간단한 알고리즘이여서 반드시 알아야 할 정렬법이다.
다시 문제로 돌아와서, 연결 리스트에 삽입 정렬을 적용해야 한다. 그러기 위해선, current 와 head 포인터가 필요하고, head는 전진시키면서, current는 필요할때마다 리스트를 거슬러 올라가며 정렬을 시도한다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = parent = ListNode(None)
while head:
while cur.next and cur.next.val < head.val:
cur = cur.next
cur.next, head.next, head = head, cur.next, head.next
cur = parent
return cur.next
Conclusion
삽입 정렬을 복습 & 연결리스트에 적용 하는 기초지만 중요한 문제였던것 같다.
SailingToTheMoooon