[Leetcode] 리트코드 - 삽입 정렬 리스트(insertion-sort-list) 파이썬(python) 풀이

문제

연결 리스트를 삽입정렬로 정렬하라.

코드

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        cur = parent = ListNode(0)

        while head:
            while cur.next and cur.next.val < head.val:
                cur = cur.next

            cur.next, head.next, head = head, cur.next, head.next

            if head and cur.val > head.val:
                cur = parent



        return parent.next



a = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
Solution().insertionSortList(a)

풀이

cur = parent = ListNode(None)

while head:
    while cur.next and cur.next.val < head.val:
        cur = cur.next

먼저, 정렬을 해야 할 대상과 정렬을 끝낸 대상, 두 그룹으로 나눠 진행한다. head는 정렬을 해야 할 대상이며, cur는 정렬을 끝낸 대상으로 정한다. while head:를 통해 정렬을 해야 할 대상 head를 반복한다.

cur와 parent는 빈 노드로 정한다. cur에는 정렬을 끝낸 연결 리스트를 추가해줄 것이고, parent는 계속 그 위치에 두어 사실상 루트를 가리키게 한다. 정렬을 끝낸 cur는 이미 정렬된 상태이므로, 정렬을 할 대상 head와 비교하면서 더 작다면 계속 cur.next를 이용해 다음으로 이동한다. 이제 정렬이 필요한 위치, 즉 cur에 삽입될 위치를 찾았다면 다음과 같이 cur 연결 리스트에 추가한다.

cur.next, head.next, head = head, cur.next, head.next

if head and cur.val > head.val:
    cur = parent

찾은 cur 위치 다음에 head가 들어가고, head.next에는 cur.next를 연결해 계속 이어지게 한다. 그리고 다음번 head는 head.next로 차례를 이어받는다. 이후에는 cur = parent를 통해 다시 처음으로 되돌아가며, 차례대로 다시 비교하게 된다.

cur = parent는 다음번 head를 비교할 떄 정렬된 노드인 cur도 다시 맨 처음으로 되돌아가라는 명령인데, cur가 head보다 클 때만 하면 되니깐 if문을 걸어주었다.

헷갈렸던 부분

cur, parent의 위치가 헷갈림. cur = cur.next는 당연히 parent가 같이 따라가는 것이 아님.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]