[LeetCode#147] Insertion Sort List

 

❒ Description

---

날짜	2024.09.27 (금)
레벨	Medium
제목	Insertion Sort List
링크	https://leetcode.com/problems/insertion-sort-list/description/
알고리즘	정렬
시간 복잡도	O(NlonN)

 

이번 문제는 삽입 정렬을 구현하면 되는 문제이다. 하지만 기본적으로 Linked List가 주어지기 때문에 까다롭다.

 

 

 

 

 

❒ 문제 및 로직 분석

---

먼저 삽입 정렬은 정렬을 해야 할 대상과 정렬을 끝낸 대상, 두 그룹으로 나눠야 한다.

• sorted : 정렬을 끝낸 대상
• head : 정렬을 해야 할 대상

그리고 몇가지 특이 케이스를 고려해야 한다.

 

1. 정렬된 결과 사이에 삽입해야 할 경우

위 경우와 같이 `sorted.next.val = 3` 이 정렬되어야 할 `head.val = 4` 보다 작은 경우에는 다음과 같이

sorted를 한 칸 앞으로 옮겨준다. 이렇게 하는 이유는 4가 3과5 사이에 위치해야 하기 때문에 그렇다.

 

2. 정렬된 결과 맨 앞에 삽입해야 할 경우

현재 sorted는 root(최종 정렬)의 일부분 이므로, 이런 경우에는 sorted를 Root로 치환해줘야 한다. 

 

 

 

 

 

❒ Solution

---

public ListNode insertionSortList(ListNode head) {
    ListNode root = new ListNode();
    ListNode sorted = root;

    while (head != null) {
        while (sorted.next != null && sorted.next.val < head.val) sorted = sorted.next;
        ListNode sortedNext = sorted.next;
        ListNode headNext = head.next;
        sorted.next = head;
        head.next = sortedNext;
        head = headNext;
        if (head != null && sorted.val > head.val) sorted = root;
    }

    return root.next;
}

 

 

 

 

 

 

---