题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
输入：lists = [] 输出：[]
示例 3：
输入：lists = [[]] 输出：[]
解题
方法一：暴力法
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: vals = [] dummy = cur = ListNode(0) for link in lists: while link: vals.append(link.val) link = link.next for val in sorted(vals): cur.next = ListNode(val) cur = cur.next return dummy.next
方法二：堆排序/优先队列
使用前要import heapq，但是在leetcode好像已经from heapq import * 了
heappush(heap,item) 往堆中插入一条新的值
item = heappop(heap) 从堆中弹出最小值
item = heap[0] 查看堆中最小值，不弹出
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: vals = [] dummy = cur = ListNode(0) for link in lists: while link: heappush(vals,link.val) link = link.next while vals: val = heappop(vals) cur.next = ListNode(val) cur = cur.next return dummy.next
其实两种方法都差不多，一个思路。
这两种方法sorted()和heapq方法在此题上差异不大,一般就使用sorted()了，但是如果在动态添加元素或者删除元素的情况下，每次都要重新sort,时间复杂度就会提高，在这种情况下使用heapq就会更加合适。
方法三：归并
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size()==0) return nullptr; return merge(lists,0,lists.size()-1); } ListNode* merge(vector<ListNode*>& lists,int left,int right){ if(left==right) return lists[left]; int mid=(left+right)>>1; ListNode* l1=merge(lists,left,mid); ListNode* l2=merge(lists,mid+1,right); return mergeTwoList(l1,l2); } ListNode* mergeTwoList(ListNode* l1,ListNode* l2){ if(!l2) return l1; if(!l1) return l2; if(l1->val<l2->val){ l1->next=mergeTwoList(l1->next,l2); return l1; }else{ l2->next=mergeTwoList(l1,l2->next); return l2; } } };
