[LeetCode] 147. Insertion Sort List

🔎 문제 링크 147. Insertion Sort List

❓ Question

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.

삽입 정렬을 이용하여 linked list를 정렬하는 문제이다.

💡 삽입 정렬
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

❗ My Solution

🤔 풀이 까지의 과정

sorting 알고리즘을 공부하는 와중에 맞닥드린 문제.
처음에는 바로 해결을 하지 못하여 사람들이 discuss에 올려둔 솔루션을 찾아보았다.
솔루션 하나로는 이해가 잘 가지 않아 여러 사람들이 올려놓을 것을 보며 이해한 것을 작성하겠다.
적어두지 않으면 다시 풀어볼 때 기억하지 못할 것 같기에...

💻 코드로 정리

📌 Solution은 다른 사람들의 것을 참고하였지만,
최종 코드는 내가 이해한 것을 바탕으로, 내가 이해하기 쉽도록 고쳐 작성하였다.

function insertionSortList(head: ListNode | null): ListNode | null {
    let sorted = new ListNode();
    let curr = head;
    
    while (curr) {
        let prev = sorted;
        
        // curr.val이 들어 갈 자리 찾기
      	// 1. prev.next, 즉 정렬된 데이터가 존재하거나, 
      	// 2. curr.val이 정렬된 데이터의 현재 포인터 값보다 큰 경우
        while (prev.next && prev.next.val < curr.val) {
      		// 다음 포인터로 넘어간다
            prev = prev.next;
        }
      
      	// 찾은 자리에 넣을 데이터.
      	// 찾은 자리 사이에 넣어야 하기 때문에, 
      	// val은 curr.val이 되고, prev의 이후 값을 next로 가지는 신규 ListNode 생성
        let prevNext = new ListNode(curr.val, prev.next); 
        // 이미 정렬한 val을 제외한 next를 다음 curr에 넣는다.
        let currContinue = curr.next; 
      
        prev.next = prevNext;
        curr = currContinue;
      	// curr의 모든 데이터를 정렬할 때 까지 반복한다.
    }
    
    return sorted.next;
};

📝 그림으로 정리

코드만 보고 이해가 가지 않아 그림으로 차근차근 그려가며 파악하였다.

🤍 정리

문제만 봤을 때 이전 노드를 찾는 방법 잘 몰라 한참 헤매었는데,
비어있는 dummy ListNode를 생성하여, 해당 ListNode에 정렬한 데이터를 넣는 것이 포인트였다.
조만간 다시 복습하여 개념을 더 확실히 이해하여 내 것으로 만들어야 겠다.