[LeetCode] #23. Merge k Sorted Lists (Priority Queue, Hard)

[Cheolsker]

제한사항

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

• 연결리스트 갯수는 최대 1만개
• 리스트들의 길이는 최대 500
• 리스트값의 범위는 -1만 ~ 1만
• 즉, 최대 시간복잡도 O(NlogN) 으로 해결가능

아이디어

1. 리스트 배열을 돌면서, 배열이 빌 때까지 루트 노드에 오름차순 순으로 노드들을 붙이기 ( O(N) )
   a. 루트 노드를 생성, 작은 노드 순서대로 여기에 붙임
   b. 리스트들의 배열이 빌 때까지 반복
   c. 리스트들을 돌면서, 가장 작은 리스트 노드 (min)를 찾음, O(1)
   d. min 노드의 다음 노드가 있으면, 해당 리스트의 head는 min.next
   e. min 노드가 마지막 노드면, 해당 리스트는 제거
   f. min 노드가 존재하면, tail에 붙임
   g. root.next 노드를 반환