Problem
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:
Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
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.
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.
Example 1:
Input: head = [4,2,1,3] Output: [1,2,3,4]Example 2:
Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5] Constraints: ・ The number of nodes in the list is in the range [1, 5000]. ・ -5000 <= Node.val <= 5000
Idea
Insertion Sort는 O(n²)인 비효율적인 정렬 알고리즘이다. 대부분은 array를 이용해서 한 번쯤 해보았을 법한 정렬 방법인데, 리스트를 이용해 정렬하는 건 익숙하지 않다.
리스트에서 Insertion Sort를 하려면 정렬된 리스트를 가리키는 포인터가 있으면 편하다. 이는 노드를 정렬할 때 삽입하기 전 노드와 그 다음 노드를 알아야 하기 때문이다. 만약 원래 주어진 리스트를 사용하면 이전 노드 포인터와 그 다음 노드 포인터를 각각 저장하느라 코드가 복잡해진다.
정렬된 리스트의 첫 번째 노드는 dummy 노드로 값이 없는 노드다. dummy 노드가 있으면 가장 작은 값을 가진 노드가 있더라도 삽입이 용이해진다.
주어진 리스트를 돌면서 해당 노드의 값을 정렬된 리스트의 노드들과 비교한다. 현재 노드가 크다면 정렬된 리스트의 다음 노드와 비교하는 걸 반복하면 된다.
만약 현재 노드보다 큰 값을 가진 노드가 나왔을 경우, 현재 노드의 next 포인터를 해당 노드로 가리키게 한다. 그리고 이전 노드의 next 포인터를 현재 노드로 가리키면 된다.
주어진 리스트를 계속 돌면서 위 과정을 반복하면 정렬이 되며, dummy 노드의 next 포인터를 리턴하면 된다.
Solution
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode res = new ListNode();
ListNode curr = head;
while (curr != null) {
ListNode prev = res;
ListNode next = curr.next;
while (prev.next != null && prev.next.val < curr.val) {
prev = prev.next;
}
curr.next = prev.next;
prev.next = curr;
curr = next;
}
return res.next;
}
}Reference
