|
| 1 | +""" |
| 2 | +Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. |
| 3 | +""" |
| 4 | + |
| 5 | +# Definition for singly-linked list. |
| 6 | +# class ListNode(object): |
| 7 | +# def __init__(self, x): |
| 8 | +# self.val = x |
| 9 | +# self.next = None |
| 10 | + |
| 11 | +from heapq import heappush, heappop, heapreplace, heapify |
| 12 | + |
| 13 | +def mergeKLists(lists): |
| 14 | + dummy = node = ListNode(0) |
| 15 | + h = [(n.val, n) for n in lists if n] |
| 16 | + heapify(h) |
| 17 | + while h: |
| 18 | + v, n = h[0] |
| 19 | + if n.next is None: |
| 20 | + heappop(h) #only change heap size when necessary |
| 21 | + else: |
| 22 | + heapreplace(h, (n.next.val, n.next)) |
| 23 | + node.next = n |
| 24 | + node = node.next |
| 25 | + |
| 26 | + return dummy.next |
| 27 | + |
| 28 | +from Queue import PriorityQueue |
| 29 | + |
| 30 | +def merge_k_lists(lists): |
| 31 | + dummy = ListNode(None) |
| 32 | + curr = dummy |
| 33 | + q = PriorityQueue() |
| 34 | + for node in lists: |
| 35 | + if node: q.put((node.val,node)) |
| 36 | + while q.qsize()>0: |
| 37 | + curr.next = q.get()[1] |
| 38 | + curr=curr.next |
| 39 | + if curr.next: q.put((curr.next.val, curr.next)) |
| 40 | + return dummy.next |
| 41 | + |
| 42 | + |
| 43 | +""" |
| 44 | +I think my code's complexity is also O(nlogk) and not using heap or priority queue, |
| 45 | +n means the total elements and k means the size of list. |
| 46 | +
|
| 47 | +The mergeTwoLists functiony in my code comes from the problem Merge Two Sorted Lists |
| 48 | +whose complexity obviously is O(n), n is the sum of length of l1 and l2. |
| 49 | +
|
| 50 | +To put it simpler, assume the k is 2^x, So the progress of combination is like a full binary tree, |
| 51 | +from bottom to top. So on every level of tree, the combination complexity is n, |
| 52 | +beacause every level have all n numbers without repetition. |
| 53 | +The level of tree is x, ie logk. So the complexity is O(nlogk). |
| 54 | +
|
| 55 | +for example, 8 ListNode, and the length of every ListNode is x1, x2, |
| 56 | +x3, x4, x5, x6, x7, x8, total is n. |
| 57 | +
|
| 58 | +on level 3: x1+x2, x3+x4, x5+x6, x7+x8 sum: n |
| 59 | +
|
| 60 | +on level 2: x1+x2+x3+x4, x5+x6+x7+x8 sum: n |
| 61 | +
|
| 62 | +on level 1: x1+x2+x3+x4+x5+x6+x7+x8 sum: n |
| 63 | +""" |
0 commit comments