[LeetCode] Merge k Sorted Lists

문제

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [   1->4->5,   1->3->4,   2->6 ] Output: 1->1->2->3->4->4->5->6

 

Approach

Min heap에 list의 앞부분을 하나씩 담은 후 answer list에 min heap의 맨 위 원소를 넣어준다.

answer에 들어간 원소는 next가 null이 아닌 경우 그 다음 원소를 다시 min heap에 넣는다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_MergeKSortedLists_MinHeap.cpp

chi3236/algorithm