Question: http://oj.leetcode.com/problems/merge-k-sorted-lists/
Question Name: Merge k Sorted Lists
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # Definition and implement of a min heap class _Heap: # Make it 1-based index heap = [None] def __init__(self): return def size(self): return len(self.heap) - 1 def _swin(self, K): while (K > 1 and self.heap[K//2].val > self.heap[K].val): self.heap[K//2], self.heap[K] = self.heap[K], self.heap[K//2] K = K//2 return def _sink(self, K): N = len(self.heap) while 2 * K < N: tempIndex = 2 * K if tempIndex + 1 < N and self.heap[tempIndex + 1].val < self.heap[tempIndex].val: tempIndex += 1 if self.heap[K].val <= self.heap[tempIndex].val: break self.heap[tempIndex], self.heap[K] = self.heap[K], self.heap[tempIndex] K = tempIndex return def add(self, item): self.heap.append(item) self._swin(len(self.heap)-1) return def delMin(self): if len(self.heap) == 2: return self.heap.pop() self.heap[1], self.heap[-1] = self.heap[-1], self.heap[1] temp = self.heap.pop() self._sink(1) return temp class Solution: # @param a list of ListNode # @return a ListNode def mergeKLists(self, lists): # Handle the special case: empty input if len(lists) == 0: return None # Initial our heap with the first node in each list heap = _Heap() for singleList in lists: if singleList != None: heap.add(singleList) # Actually empty input if heap.size() == 0: return None # Build the head of the result list head = heap.delMin() if head.next != None: heap.add(head.next) # Merge the remaining part of all the lists current = head while heap.size() != 0: current.next = heap.delMin() current = current.next if current.next != None: heap.add(current.next) return head |