23.md

23. Merge k Sorted Lists

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

my thoughts:

1. build a balanced BST for the listnodes. if only one node just append it to res; otherwise, append the min, remove min from the tree; if min has next, add its next back to the tree. repeat till tree contains only one node. ---do not know how to build AVL tree.
O(m*n*logn) 

2. when listnodes has only one node, append the node to res; append min val of nodes to res and min = min.next;
O(n^2*m) -- find min is n, each time reduce the problem set by 1, so to clear each layer, it is n^2

3. use minheap to figure out min at logn time.

my solution:

**********TLE
# 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
        """
        if not lists:
            return None
        res = ListNode(-1)
        l = len(lists)
        def helper(lists, res, l):
            onlyOne = True
            minNode = 0
            for i in range(1,l):
                if lists[i]:
                    if not lists[minNode]:
                        minNode = i
                        continue
                    onlyOne = False
                    if lists[i].val<lists[minNode].val:
                        minNode = i
            if onlyOne:
                res.next = lists[minNode]
                return
            else:
                res.next = ListNode(lists[minNode].val)
                lists[minNode] = lists[minNode].next
                helper(lists, res.next, l)
                
        helper(lists, res, l)
        return res.next
		
		
**********942ms		
# 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
        """
        if not lists:
            return None
        
        nlist = [x for x in lists if x]
        if not nlist:
            return None
        
        heap = sorted(nlist, key = lambda x:x.val)
        res = ListNode(-1)
        p1 = res
        #print [x.val for x in heap]
        
        def mheapify(heap):
            if len(heap) == 1:
                return
            cur = 0
            while True:
                child_l = cur*2 + 1
                child_r = cur*2 + 2
                if child_l >= len(heap):
                    return
                elif child_l == len(heap)-1:
                    if heap[cur].val <= heap[child_l].val:
                        return
                    else:
                        heap[cur], heap[child_l] = heap[child_l], heap[cur]
                        return
                else:
                    if heap[child_l].val<heap[child_r].val:
                        if heap[child_l].val < heap[cur].val:
                            heap[child_l], heap[cur] = heap[cur], heap[child_l]
                            cur = child_l
                            continue
                        else:
                            return
                    else:
                        if heap[child_r].val < heap[cur].val:
                            heap[child_r], heap[cur] = heap[cur], heap[child_r]
                            cur = child_r
                            continue
                        else:
                            return
                        
        while len(heap)>1:
            p1.next = heap[0]
            p1 = p1.next
            if heap[0].next:
                heap[0] = heap[0].next
                mheapify(heap)
            else:
                heap=heap[-1:]+heap[1:-1]                
                mheapify(heap)
            temp = []
            t = res.next
            #while t:
            #    temp.append(t.val)
            #    t = t.next
            #print temp
        p1.next = heap[0]
        
        return res.next

my comments:

from other ppl's solution:

1. use built in heapq,119ms:
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

import heapq

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        dummy = ListNode(0)
        head = dummy
        
        for list in lists:
            if list:
                heapq.heappush(heap,  (list.val, list))
        
        while heap:
            temp = heapq.heappop(heap)[1]
            head.next = temp
            head = head.next
            if temp.next:
                heapq.heappush(heap, (temp.next.val, temp.next))
        
        
        return dummy.next
		
2. muhaha, time O((n*m)log(n*m)) is kicking ass, 109ms:
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        self.nodes = []
        head = point = ListNode(0)
        for l in lists:
            while l:
                self.nodes.append(l.val)
                l = l.next
        for x in sorted(self.nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next