[LeetCode] 147. Insertion Sort List

😎풀이

해당 문제는 삽입 정렬을 연결형 노드를 통해 구현하는 문제이다.

풀이 과정은 다음과 같음

1. 가장 왼쪽에 위치할 노드 생성
2. 매 반복마다 1의 노드를 통해 좌측부터 현재 노드와 값을 비교해가며 이전 노드 탐색
3. 이전 노드와 현재 노드를 연결
4. 기존 현재 노드의 다음 노드를 탐색

function insertionSortList(head: ListNode | null): ListNode | null {
    if(!head || !head.next) return head
    // 가장 왼쪽에 위치할 노드 생성
    let mock = new ListNode(Number.MIN_SAFE_INTEGER)
    let cur = head
    while(cur) {
        // 미리 다음 노드 저장
        const next = cur.next
        // 가장 왼쪽 자리 할당
        let prev = mock
        // 현재 값과 비교하며 바로 이전 노트까지 탐색
        while(prev.next && prev.next.val < cur.val) {
            prev = prev.next
        }
        // 현재 노드와 이전 노드 연결
        cur.next = prev.next
        prev.next = cur
        // 다음 노드로 이동
        cur = next
    }
    return mock.next
};