[leetcode][23] Merge k Sorted Lists

문제 : leetcode.com/problems/merge-k-sorted-lists/

---

k개의 오름차순정렬된 ListNode 포인터 배열이 주어진다.

배열의 모든 ListNode를 오름차순 정렬된 하나의 ListNode로 만들어라.

---

오름차순 정렬되어있기 때문에 k개의 배열을 탐색하면서 가장 작은 노드를 구하고 이를 정답 리스트노드 다음에 추가한다. 추가한 노드는 다시 탐색되지 않게 하기 위해 next 노드를 보게 갱신한다.

 

항상 k개의 배열을 탐색하는데, 이를 정답 ListNode를 만들때까지 실행될 것이기 때문에.

N = k, M = 정답 ListNode 배열 크기라 할 때, 시간복잡도는 O(NM).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/23.%20Merge%20k%20Sorted%20Lists.cpp

---

알고리즘 자체는 간단하다. 구현할 수 있는가를 보는 문제라고 볼 수 있을듯.

배열 탐색으로 풀었는데, 우선순위큐에 넣어서도 풀더라.