23. 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

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

"""

解法1：效率低下 时间复杂度O（m*n） 5452 ms
①遍历列表
②比较每个元素的头节点
③找到最小的一个节点
④最小的结点，头节点指向下一个节点，并插入新的列表
"""
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        
        dummy = l = ListNode(None)           
        flag = 1
        while flag:
            flag = 0
            min = 123123123123
            for i, head in enumerate(lists):
                if head:
                    if head.val < min:    #每次都找列表头中最小的一个
                        min = head.val
                        index = i
                    flag = 1
            if flag == 1:
                l.next = lists[index]
                l = l.next    
                lists[index] = lists[index].next
       
        return dummy.next         

"""
解法2：sort的时间复杂度 Runtime: 52 ms, faster than 99.61% of Python online submissions for Merge k Sorted Lists.
①遍历列表
②每个链表的节点，放入list
③按值排序
④重新建立链表
"""

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        
        res = []
        for head in lists:
            while head:
                res.append((head.val, head))
                head = head.next
            
        
        res.sort(key=lambda x: x[0])
        
        dummy = l = ListNode(None)
        
        for node in res:
            l.next = node[1]
            l = l.next
        
        return dummy.next