[LeetCode][python3]0023. Merge k Sorted Lists

Start the journey
N2I -2020.07.04

1. A better Solution

class Solution(object):
    def mergeKLists(self, lists):
        l = []
        for list_node in lists:
            node = list_node
            while node:
                l.append(node)
                node = node.next
        if not l:
            return None
        l.sort(key=lambda x: x.val)
        for i, node in enumerate(l):
            if i == len(l)-1:
                node.next = None
            else:
                node.next = l[i+1]
        return l[0]

Explanation:

The easiest and fastest way to solve this problem, is to ignore the link list type and sort the nodes in an array. The first part of this solution is to put all nodes into one array. After sorting the array by key=lambda x:x.val, link them together into one link list in ascending order.

2. Other Solution

from heapq import heappop, heappush
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        dummy = cur = ListNode(0)
        heap = []
        for l in lists:
            while l:
                heappush(heap, l.val)
                l = l.next
        while heap:
            cur.next = ListNode(heappop(heap))
            cur = cur.next   
        return dummy.next

3. My dummy Solution

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        dic={}
        for index,item in  enumerate(lists):
            if item != None:
                dic[index]=item.val
        h=p=ListNode()
        while dic:
            index,item=min(dic.items(),key= lambda a: a[-1])
            p.next=ListNode(item)
            p=p.next
            lists[index]=lists[index].next
            if lists[index]==None:
                del dic[index]
            else:
                dic[index]=lists[index].val
        h=h.next
        return h