23. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

 

Constraints:

• 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 won't exceed 10^4.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        
        res = []
        
        for l in lists:
            while l:
                res.append(l.val)
                l = l.next
                
        res = sorted(res)

        if not res: return
        
        head = ListNode(res[0])
        cur = head
        
        for v in res[1:]:
            cur.next = ListNode(v)
            cur = cur.next
        
        return head

- Runtime: 80 ms, faster than 96.39% of Python online submissions for Merge k Sorted Lists.

 Memory Usage: 22.2 MB, less than 31.52% of Python online submissions for Merge k Sorted Lists.

- 솔루션들을 체크했을 땐, heap queue를 많이 사용하거나, divide conquer를 많이 사용했다.

 결국 O(nlogn)은 같을텐데, 내가 짠 코드도 전체 순회(N) + sorted(NlogN) + 전체 리스트노드 추가(N)이라

 시간 복잡도는 같다고 생각된다.