[Leetcode] 147. Insertion Sort List

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

---

단일 linked list의 헤드가 주어질 때 삽입 정렬을 이용하여 이들을 정렬한뒤 정렬된 linked list의 헤드를 반환하라.

---

정렬된 링크드 리스트의 헤드를 저장하기 위해 ListNode를 하나 만들고 이 노드의 주소값을 newHead 변수에 저장한다.

원본 head의 노드를 처음부터 하나씩 정렬시켜야 하므로 앞에있는 노드부터 하나씩 탐색하며 newHead를 헤드로 하는 링크드 리스트의 적절한 위치에 연결해준다. 탐색하는 노드의 포인트를 originNode라 하자.

정렬된 링크드 리스트의 적절한 위치를 찾을 때 노드를 적절한 위치에 넣기 위해서는 해당 노드의 앞에 위치하는 노드를 알아야 한다.

예를 들어, 2 -> 4 -> 3 인 링크드 리스트가 있을 때, 3 노드를 적절한 위치에 넣기 위해서는 2와 4 사이에 들어가야 하는데 2 노드의 next에 3을 연결하고 3의 next에 4를 연결해야 하므로 2노드의 포인트 주소를 알고 있어야 한다. 따라서 이 때 2에 해당하는 노드의 포인트를 newPrev라 하겠다.

originNode->next = newPrev->next; // 3->4 연결
newPrev->next = originNode; // 2->3 연결

적절한 위치를 찾은 뒤 위와 같이 노드의 연결관계를 재 설정해준다.

 

적절한 위치를 찾는 방법은 newPrev->next의 val가 탐색노드인 originNode의 val보다 큰 경우를 찾을 때까지(ex, newPrev = 2일 때, newPrev->next->val 은 4이므로 이는, originNode->val인 3보다 크기 때문에 newPrev가 2인 경우 적절한 위치가 된다.)

newPrev를 newHead부터 시작하여 더이상 탐색할 노드가 없을때까지 next 노드를 탐색해나간다.

 

시간복잡도는 O(2N) = O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/147.%20Insertion%20Sort%20List.cpp