解法1 利用heap,手动写出
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
|
import heapq class (object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return None dummy = ListNode(0) cur = dummy heap = [] for index, head in enumerate(lists): if head: heapq.heappush(heap, [head.val, head]) while heap: _, node = heapq.heappop(heap) if node.next: heapq.heappush(heap, [node.next.val, node.next]) cur.next = node cur = node return dummy.next
|
解法2 参考了别人的答案。这个解法是divide and conquer,就是把大问题划分成小问题递归解决。这样的做法在tree的题目里很多,要仔细体会。此题加入V3
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
|
import heapq class (object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return None if len(lists) == 1: return lists[0] mid = len(lists) / 2 left = self.mergeKLists(lists[:mid]) right = self.mergeKLists(lists[mid:]) return self.merge(left, right) def merge(self, l1, l2): dummy = ListNode(0) cur = dummy while l1 and l2: if l1.val > l2.val: cur.next = l2 l2 = l2.next else: cur.next = l1 l1 = l1.next cur = cur.next if l1: cur.next = l1 if l2: cur.next = l2 return dummy.next
|
近期评论