[코테] 리트코드 정렬 147. Insertion Sort List

147. Insertion Sort List

문제 링크

https://leetcode.com/problems/insertion-sort-list/description/

문제 설명

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head.

The steps of the insertion sort algorithm:

1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
3. It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

제한 사항

• The number of nodes in the list is in the range [1, 5000].
• -5000 <= Node.val <= 5000

입출력 예 #1

1. Input : head = [4,2,1,3]
2. Output : [1,2,3,4]

입출력 예 #2

1. Input : head = [-1,5,3,4,0]
2. Output : [-1,0,3,4,5]

문제 풀이

cur은 정렬을 끝낸 연결 리스트를 추가, parent는 루트, head는 정렬할 노드를 설정하며 반복한다.

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[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

            # 필요한 경우에만 cur 포인터가 되돌아가도록 처리
            if head and cur.val > head.val:
                cur = parent
        return parent.next