147. Insertion Sort List

문제 링크: https://leetcode.com/problems/insertion-sort-list/

아래와 같이 정의된 singly-linked list를 Insertion Sort를 이용해 정렬하는 문제이다.

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; }
}

배열에서 insertion sort를 수행하는 것과 다른 점은 삽입할 현재 원소인 currNode를 앞으로 한 칸씩 옮기면서 다른 원소들과 비교할 수 없다는 점이다.

따라서 정렬 전 list에서 currNode의 바로 전 원소를 prevNode라고 하면, list의 head에서부터 prevNode까지 앞에서 부터 비교해 삽입할 위치를 찾기로 했다.

이때, currNode는 head에서부터 삽입할 위치의 이전 노드까지를 알 수 없으므로 정렬된 list를 저장할 sortedList라는 ListNode를 새로 만들었고, 주어진 list를 순회하면서 sortedList에 ListNode를 하나씩 더해가는 방식으로 구현했다.

문제를 푸는 방식을 정리해보면,

1. 정렬된 linked list를 저장할 sortedList를 선언한다.
2. input으로 주어진 list를 순회하면서, 각 ListNode를 sortedList에 삽입할 위치를 찾는다.
3. input list의 순회가 끝나면, sortedList는 정렬된 linked list가 된다.

programming tips

singly-linked-list에 새로운 원소를 삽입할 때, pair of pointers(prev → next)를 이용하면 편리하다.
두 포인터의 사이에 새로운 원소를 삽입할 place-holder 같은 역할을 하는 것이다. (prev → new_node → next)

Solution

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode sortedList = new ListNode();
        ListNode currNode = head;
        
        while (currNode != null) { // iterate over the input list
            ListNode prevNode = sortedList;
            
            while (prevNode.next != null && prevNode.next.val < currNode.val) { 
                // find the position to insert the current node
                prevNode = prevNode.next;
            }
            ListNode nextNode = currNode.next;
            
            // insert the current node to the new list
            currNode.next = prevNode.next;
            prevNode.next = currNode;
            
            currNode = nextNode; // moving on to the next iteration
        }
        
        return sortedList.next;
    }
}