【Day 69 】2021-11-17 - 23. 合并 K 个排序链表 #88
Comments
思路:由于需要将k个升序链表合并成一个升序链表, 可以使用 方法: 堆排序思路: 借助priority_queue, 使用node的val构造一个小顶堆。 创建虚拟头结点，取出最小值对应的结点指针，将其挂接在游标指针上。 只要挂接点后面还有结点，则将其压入queue中，继续从中拿出最小值，循环往复。 代码:实现语言: C++ class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty())
return NULL;
ListNode* res;
auto cmp = [](ListNode* n1, ListNode* n2)
{
return n1->val > n2->val;
};
/* 使用node的val构造一个小顶堆 */
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> nodesQ(cmp);
for (auto list : lists)
{
if (list != NULL)
{
nodesQ.push(list);
}
}
ListNode* fakeHead = new ListNode(-1); /* 创建虚拟头结点 */
ListNode* cur = fakeHead;
while (!nodesQ.empty())
{
cur->next = nodesQ.top(); /* 取出最小值对应的结点指针，挂接在游标指针上 */
cur = cur->next;
nodesQ.pop();
if (cur->next != NULL) /* 只要挂接点后面还有结点，则将其压入栈，继续从中拿出最小值，循环往复 */
{
nodesQ.push(cur->next);
}
}
return fakeHead->next;
}
};复杂度分析:
|
关键点代码
C++ Code: /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
struct cmp
{
bool operator()(ListNode* & node1, ListNode*& node2)
{
return node1->val > node2->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
for(int i=0; i< lists.size(); i++)
{
if(lists[i])
pq.push(lists[i]);
}
if(pq.size()==0)
return NULL;
ListNode* ret = pq.top();
ListNode* prev = NULL;
while(pq.size())
{
ListNode* top = pq.top();
pq.pop();
if(prev!=NULL)
prev->next = top;
prev = top;
if(top->next)
{
pq.push(top->next);
}
}
return ret;
}
};
|
thoughtsk路归并 codeclass Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
"""
merge sort
"""
if not lists:
return None
def merge_two_lists(l1, l2):
head = current_node = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
current_node.next = l1
l1 = l1.next
else:
current_node.next = l2
l2 = l2.next
current_node = current_node.next
current_node.next = l1 or l2
return head.next
interval = 1
while interval < len(lists):
for i in range(0, len(lists), interval * 2):
lists[i] = merge_two_lists(
lists[i], lists[i + interval] if i + interval < len(lists) else None
)
interval *= 2
return lists[0]complexity时间复杂度O(nlgk) 空间复杂度O(1) |
from heapq import heappush, heappop
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
dummy = tail = ListNode()
heap = []
for i in range(len(lists)):
head = lists[i]
if not head:
continue
heappush(heap, (head.val, i, head))
while heap:
_, index, node = heappop(heap)
tail.next = node
tail = tail.next
if node.next:
heappush(heap, (node.next.val, index, node.next))
return dummy.next |
# 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:
heap = []
for i, l in enumerate(lists):
if l:
heappush(heap, (l.val, i))
head = ListNode()
cur = head
while heap:
_, i = heappop(heap)
node = lists[i]
cur.next = node
cur = cur.next
if node.next:
heappush(heap, (node.next.val, i))
lists[i] = node.next
return head.nextComplexity: O(Llgk); O(k) , L is the total number of nodes in the k linked lists. |
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> (a.val - b.val));
for (ListNode node : lists) {
if (node != null) {
minHeap.offer(node);
}
}
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (!minHeap.isEmpty()) {
ListNode temp = minHeap.poll();
cur.next = temp;
if (temp.next != null) {
minHeap.offer(temp.next);
}
cur = cur.next;
}
return dummy.next;
}
// time O(nlogn) space O(n) |
link:https://leetcode.com/problems/merge-k-sorted-lists/ 代码 Javascriptfunction merge (left, right) {
if (!left) {
return right;
} else if (!right) {
return left;
} else if (left.val < right.val){
left.next = merge(left.next, right);
return left;
} else {
right.next = merge(left, right.next);
return right;
}
}
function helper(lists, start, end) {
if (start === end) {
return lists[start];
} else if (start < end) {
const mid = parseInt((start + end) / 2);
const left = helper(lists, start, mid);
const right = helper(lists, mid + 1, end);
return merge(left, right);
} else {
return null;
}
}
const mergeKLists = function(lists) {
return helper(lists, 0, lists.length - 1);
}; |
Idea
Pythonclass Solution(object):
def mergeKLists(self, lists):
heap = []
heapq.heapify(heap)
for i in range(len(lists)):
if lists[i]!=None:
heapq.heappush(heap, [lists[i].val, i])
lists[i] = lists[i].next
def getNext():
if heap == []:
return None
else:
[val, index] = heapq.heappop(heap)
if lists[index]!=None:
heapq.heappush(heap, [lists[index].val, index])
lists[index] = lists[index].next
return ListNode(val, getNext())
return getNext()JavaScriptvar mergeKLists = function(lists) {
const q = new MinPriorityQueue({priority: (node) => node.val});
for (let list of lists){
list && q.enqueue(list);
};
let dummy = new ListNode();
let cur = dummy
while(q.size()){
let list = q.dequeue().element;
cur.next = new ListNode(list.val);
cur = cur.next;
list.next && q.enqueue(list.next);
};
return dummy.next;
}; |
ThinkingDivide and concur. Code# 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:
if not lists:
return None
if len(lists) == 1:
return lists[0]
mid = len(lists)//2
l1, l2= self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:])
return self.merge(l1, l2)
def merge(self, l1, l2):
head = curr = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return head.next
|
|
Idea: divide and conquer + |
|
min heap # 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:
h = []
for i, li in enumerate(lists):
if li:
heappush(h, (li.val, i))
dummy = ListNode(0)
cur = dummy
while h:
val, i = heappop(h)
cur.next = ListNode(val)
if lists[i].next:
heappush(h, (lists[i].next.val, i))
lists[i] = lists[i].next
cur = cur.next
return dummy.next |
代码class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
for(ListNode list : lists) {
if(list != null) {
queue.add(list);
}
}
while(!queue.isEmpty()) {
cur.next = queue.poll();
cur = cur.next;
if(cur.next != null) {
queue.add(cur.next);
}
}
return dummy.next;
}
}复杂度分析时间复杂度O(nlogk) k == lists.length 空间复杂度O(n) |
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
dummy = ListNode(0)
temp = dummy
heap = []
for index,node in enumerate(lists):
if node:
heapq.heappush(heap,(node.val, index, node))
while heap:
_, curindex, curnode= heapq.heappop(heap)
temp.next = curnode
temp = temp.next
if curnode.next:
heapq.heappush(heap,(curnode.next.val, index, curnode.next))
return dummy.next |
思路
代码
# 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:
n = len(lists)
if n == 0:
return None
elif n == 1:
return lists[0]
elif n == 2:
return self.merge2lists(lists[0], lists[1])
else:
mid = n // 2
return self.merge2lists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]))
def merge2lists(self, list1, list2):
dummy = ListNode()
curr = dummy
while list1 and list2:
if list1.val <= list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
if list1:
curr.next = list1
if list2:
curr.next = list2
return dummy.next |
解题思路分治。把k个lists两两分组，最后一组可能只有1个list，然后进行合并组成 代码class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
if (k == 0) return null;
if (k == 1) return lists[0];
// divide the lists into len groups, each has 2 least (the last group may contain only 1)
int len = (int) Math.ceil(k / 2.0); // use 2.0 here because ceil only works for double
ListNode[] merged = new ListNode[len];
// merge every 2 lists in the groups and store them in merged array
for (int i = 0; i < len; i++) {
// if k is odd and there is only one list left in the ListNode array, merge it with null
if (k % 2 == 1 && i == len - 1) {
merged[i] = mergeTwoLists(lists[2 * i], null);
}
// merge every two lists
else {
merged[i] = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
}
}
// recursion, merge the remaining lists
return mergeKLists(merged);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode();
ListNode cur = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
cur = cur.next;
}
else {
cur.next = l2;
l2 = l2.next;
cur = cur.next;
}
}
if (l1 != null) {
cur.next = l1;
}
if (l2 != null) {
cur.next = l2;
}
return dummyHead.next;
}
}复杂度分析
|
Intuitioncan be done by two approaches.
Algorithm in python3Complexity Analysis for divide and conquer
|
思路分治 代码/*
* @lc app=leetcode id=23 lang=javascript
*
* [23] Merge k Sorted Lists
*
* https://leetcode.com/problems/merge-k-sorted-lists/description/
*
*/
function mergeTwoLists(l1, l2) {
const dummyHead = {};
let current = dummyHead;
// l1: 1 -> 3 -> 5
// l2: 2 -> 4 -> 6
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
current.next = l1; // 把小的添加到结果链表
current = current.next; // 移动结果链表的指针
l1 = l1.next; // 移动小的那个链表的指针
} else {
current.next = l2;
current = current.next;
l2 = l2.next;
}
}
if (l1 === null) {
current.next = l2;
} else {
current.next = l1;
}
return dummyHead.next;
}
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
// 图参考： https://zhuanlan.zhihu.com/p/61796021
if (lists.length === 0) return null;
if (lists.length === 1) return lists[0];
if (lists.length === 2) {
return mergeTwoLists(lists[0], lists[1]);
}
const mid = lists.length >> 1;
const l1 = [];
for (let i = 0; i < mid; i++) {
l1[i] = lists[i];
}
const l2 = [];
for (let i = mid, j = 0; i < lists.length; i++, j++) {
l2[j] = lists[i];
}
return mergeTwoLists(mergeKLists(l1), mergeKLists(l2));
};复杂度
|
# similar to merge sort
# divide lists to half and merge both halves together
# time: O(nlogn), n: total number of elements
# space: O(1)
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists: return None
# divid and conquer
if len(lists) == 1: return lists[0]
# if len(lists) == 2: return self.merge_2_lists(lists[0], lists[1])
mid = len(lists) // 2
left_merged = self.mergeKLists(lists[0:mid])
right_merged = self.mergeKLists(lists[mid:])
return self.merge_2_lists(left_merged, right_merged)
def merge_2_lists(self, l1, l2):
if not l1: return l2
if not l2: return l1
if l1.val < l2.val:
l1.next = self.merge_2_lists(l1.next, l2)
return l1
else:
l2.next = self.merge_2_lists(l1, l2.next)
return l2 |
Java Code: /**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
if (o1.val < o2.val) return -1;
else if (o1.val == o2.val) return 0;
else return 1;
}
});
ListNode dummy = new ListNode(0);
ListNode p = dummy;
for (ListNode node : lists) {
if (node != null) queue.add(node);
}
while (!queue.isEmpty()) {
p.next = queue.poll();
p = p.next;
if (p.next != null) queue.add(p.next);
}
return dummy.next;
}
} |
思路分治 Python代码# 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:
def mg(l,r):
if l==None:
return r
elif r==None:
return l
elif l.val<=r.val:
n=mg(l.next,r)
l.next=n
return l
else:
n=mg(r.next,l)
r.next=n
return r
if len(lists)==0:
return None
if len(lists)==1:
return lists[0]
mid=len(lists)//2
left=lists[:mid]
right=lists[mid:]
l=self.mergeKLists(left)
r=self.mergeKLists(right)
return mg(l,r) |
思路一开始没想到分治法，觉得从k个链表里取他们首节点中最小的，也就是在n个元素里找最小的，因为每个元素都要来一次，那时间复杂度就是O(nk^2)呀，还能比这更快？这题跟分治法有啥关系啊？ 后来才发现自己太naive了，这个题目要把它想象成是归并排序，两两合并，合并再合并，最后得到一个答案。 首先说下上面的思路，它和这个思路复杂度是一样的：两个链表合并，再把结果和第三个链表合并，依次合并得到答案。这个复杂度是O(n)+O(2n)+...+O(kn)(链表长度依次增长，所以复杂度也是O(nk^2) 而归并的话，关键点在于链表长度增长的速度会很慢，它是两两合并，复杂度是O(nk)+O(2nk/2)+O(4nk/4)+...，有logk项(深度为logk)，结果则是O(nklogk) 这里还提供一种开根号的思路，不是将链表二分，而是根号等分，比如有256个链表，那么把它分成16组，每组16个链表，然后递归调用，即16组继续分成4组，也就是256->16->4->2，这个复杂度就是O(nk)+O(n21/2k)+O(n41/4k)+O(n16*1/16k)...，关键在于它只有loglogk项，所以复杂度来到了O(nkloglogk)，收敛会更快，当然实际跑测试用例会发现这种理想状态比较难得，比如长度为17，就会分成4,4,4,4,1，会多一些边界情况要处理，效果往往会退化。在lc的用例上跑是比二分要慢一点的 代码class Solution:
def mergeKLists1(self, lists: List[ListNode]) -> ListNode:
points = [node for node in lists if node]
if len(points) == 0:
return None
ans = ListNode()
tmp = ans
min_i = -1
while points:
min_point = ListNode(float('inf'))
for i, point in enumerate(points):
if point.val < min_point.val:
min_point = point
min_i = i
tmp.next = min_point
tmp = tmp.next
points[min_i] = points[min_i].next
if not points[min_i]:
points.remove(None)
return ans.next
def mergeKLists2(self, lists: List[ListNode]) -> ListNode:
points = [node for node in lists if node]
if len(points) == 0:
return None
def merge(lists: List[ListNode]):
if len(lists) == 1:
return lists[0]
elif len(lists) == 2:
ans = ListNode(0)
tmp = ans
i, j = lists[0], lists[1]
while i and j:
if i.val < j.val:
tmp.next = i
i = i.next
else:
tmp.next = j
j = j.next
tmp = tmp.next
tmp.next = i if i else j
return ans.next
else:
mid = len(lists) // 2
return merge([merge(lists[:mid]), merge(lists[mid:])])
return merge(lists)
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# 根号替代二分法
points = [node for node in lists if node]
if len(points) == 0:
return None
def merge(lists: List[ListNode]):
if len(lists) == 1:
return lists[0]
elif len(lists) == 2:
ans = ListNode(0)
tmp = ans
i, j = lists[0], lists[1]
while i and j:
if i.val < j.val:
tmp.next = i
i = i.next
else:
tmp.next = j
j = j.next
tmp = tmp.next
tmp.next = i if i else j
return ans.next
else:
sqrt = int(round((math.sqrt(len(lists)))))
return merge(
[
merge(lists[sqrt * i: sqrt * (i + 1)])
for i in range(sqrt + 1)
if len(lists[sqrt * i:sqrt * (i + 1)])
]
)
return merge(lists)复杂度SC: O(1)，我直接用原有链表上的节点保存的结果，没有重新开辟空间 |
|
思路：一开始可以调用N次合并两个由虚数组，但是这样的时间复杂度太高了。打到了n² type Iheap []*ListNode
func (h Iheap) Len() int{return len(h)}
func (h Iheap) Less(i,j int) bool {return h[i].Val < h[j].Val}
func (h Iheap) Swap(i,j int){h[i],h[j] = h[j],h[i]}
func (h *Iheap) Push(x interface{}){
*h = append(*h, x.(*ListNode))
}
func(h *Iheap)Pop() interface{}{
out := *h
x := out[len(out)-1]
*h = out[:len(out)-1]
return x
}
func mergeKLists(lists []*ListNode) *ListNode {
if lists == nil || len(lists) == 0{
return nil
}
var h Iheap
heap.Init(&h)
for _,list := range lists{
if list != nil{
heap.Push(&h,list)
}
}
dummy := &ListNode{}
p := dummy
for h.Len() > 0{
min := heap.Pop(&h).(*ListNode)
p.Next = min
p = p.Next
if min.Next != nil{
heap.Push(&h,min.Next)
}
}
return dummy.Next
}时间复杂度：O（nlogn） |
|
思路 实现语言: C++
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty())
return NULL;
ListNode* res;
auto cmp = [](ListNode* n1, ListNode* n2)
{
return n1->val > n2->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> nodesQ(cmp);
for (auto list : lists)
{
if (list != NULL)
{
nodesQ.push(list);
}
}
ListNode* fakeHead = new ListNode(-1);
ListNode* cur = fakeHead;
while (!nodesQ.empty())
{
cur->next = nodesQ.top();
cur = cur->next;
nodesQ.pop();
if (cur->next != NULL)
{
nodesQ.push(cur->next);
}
}
return fakeHead->next;
}
};复杂度分析 |
|
不会归并，只会数组做法 class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<int> arr;
for (int i = 0; i < lists.size(); i++) {
auto head = lists[i];
while(head) {
arr.push_back(head->val);
head = head->next;
}
}
sort(arr.begin(), arr.end());
ListNode* dummy = new ListNode(-1);
auto cur = dummy;
for (int i = 0; i < arr.size(); i++) {
cur = cur->next = new ListNode(arr[i]);
}
return dummy->next;
}
}; |
思路归并排序 代码class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
return mergeSort(lists, 0, lists.length - 1);
}
private ListNode mergeSort(ListNode[] lists, int start, int end) {
if (start >= end) {
return lists[start];
}
int mid = start + (end - start) / 2;
ListNode l1 = mergeSort(lists, start, mid);
ListNode l2 = mergeSort(lists, mid + 1, end);
ListNode dummy = new ListNode(-1);
ListNode node = dummy;
while (l1 != null || l2 != null) {
int val1 = l1 != null ? l1.val : Integer.MAX_VALUE;
int val2 = l2 != null ? l2.val : Integer.MAX_VALUE;
if (val1 <= val2) {
node.next = l1;
l1 = l1.next;
} else {
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
return dummy.next;
}
}
|
Idea:Divide and conquer. Merge 2 lists at once until we merge all lists Code:# 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[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return None
n = len(lists)
while n >= 1:
for i in range((n+1)//2):
if i + (n+1)// 2 < n:
lists[i] = self.merge2Lists(lists[i], lists[i + (n+1)// 2])
if n == 1:
break
n = (n + 1)//2
return lists[0]
def merge2Lists(self, list1, list2):
head = ListNode(0)
dummy = head
while list1 and list2:
if list1.val > list2.val:
dummy.next = ListNode(list2.val)
list2 = list2.next
else:
dummy.next = ListNode(list1.val)
list1 = list1.next
dummy = dummy.next
while list1:
dummy.next = ListNode(list1.val)
dummy = dummy.next
list1 = list1.next
while list2:
dummy.next = ListNode(list2.val)
dummy = dummy.next
list2 = list2.next
return head.nextComplexity:Time: O(N log k). N: total nodes of all linked-lists. k: the number of linked-lists |
思路每次将 linkedlist 分为 [l, mid] 和 [mid+1, r], 分别进行 merge, 最后用 merge 两个 linkedlist 方法 merge 返回的左右两个 linkedlist base case 是 当 l == r 的时候, 代表只有一个 linkedlist, 那么 返回 list[l] 这个 linkedlist 本身即可 注意边界条件, 要判断空集的情况 # 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:
if not lists:
return None
def merge(ll, l, r):
if l == r:
return ll[l]
elif r - l == 1:
return mergetwoll(ll[l], ll[r])
else:
mid = (l+r) // 2
L = merge(ll, l, mid)
R = merge(ll, mid+1, r)
return mergetwoll(L, R)
def mergetwoll(l1, l2):
head = ListNode()
tmp = head
while l1 or l2:
if (l1 and l2 and l1.val < l2.val) or (not l2):
tmp.next = l1
l1 = l1.next
else:
tmp.next = l2
l2 = l2.next
tmp = tmp.next
return head.next
head = merge(lists, 0, len(lists)-1)
return head复杂度时间复杂度: O(kn logk) 第一轮合并 k/2 组链表, 每组的时间代价是 O(2n), 第二轮合并 k/4 组链表, 每组的时间代价是 O(4n)... 总代家是 O( sum i = [1, inf] k/(2^i) * 2 ^i n) = O(kn logk) 画出递归树的话就是每层复杂度都是 O(nk), 递归深度为 O(logk) 空间复杂度: 递归栈的空间复杂度是 O(logk) |
【day69】题目地址（23. 合并 K 个排序链表）https://leetcode-cn.com/problems/merge-k-sorted-lists/ 思考：合并排序的思路 两两合并 class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# 1.归并两两排序
list_node = [ node for node in lists if node]
if len(list_node) == 0:
return None
def merge2list(lists: List[ListNode]):
#判断情况
if len(lists) == 1 :
return lists[0]
elif len(lists) == 2 :
ans = ListNode(0)
tmp = ans
list1 ,list2 = lists[0], lists[1]
while list1 and list2:
if list1.val < list2.val:
tmp.next = list1
list1 = list1.next
else:
tmp.next = list2
list2 = list2.next
tmp = tmp.next
tmp.next = list1 if list1 else list2
return ans.next
else:
mid = len(lists) // 2
return merge2list([ merge2list(lists[:mid]), merge2list(lists[mid:])])
return merge2list(lists)复杂度分析：
|
思路归并排序的思路，将数组分为两部分分别进行合并 class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return mergeKListsOfRange(lists,0,lists.length-1);
}
public ListNode mergeKListsOfRange(ListNode[] lists,int start,int end) {
if(start>end)return null;
if(start == end)return lists[start];
if(start + 1 == end)return merge(lists[start],lists[end]);
int mid = (end -start)/2+start;
ListNode left = mergeKListsOfRange(lists,start,mid-1);
ListNode right = mergeKListsOfRange(lists,mid,end);
return merge(left,right);
}
ListNode merge(ListNode left,ListNode right){
if(left == null)return right;
if(right == null)return left;
ListNode head = new ListNode();
ListNode cur = head;
while(left!=null && right!=null){
if(left.val<=right.val){
cur.next = left;
cur = left;
left = left.next;
}else {
cur.next = right;
cur = right;
right = right.next;
}
}
if(left!=null){
cur.next = left;
}else {
cur.next = right;
}
return head.next;
}
}
|
思路堆排 ##d代码 class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
l = []
for i in lists:
if i is not None:
l.append(i)
if len(lists) == 0:
return None
heap = [(node.val, node) for node in l]
heapq.heapify(heap)
head = start = ListNode(0)
while len(heap) > 0:
val, node = heapq.heappop(heap)
start.next = node
start = start.next
if node.next:
heapq.heappush(heap, (node.next.val, node.next))
return head.next |
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r){
if (l == r){
return lists[l];
}
if (l > r){
return null;
}
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode mergeTwoLists(ListNode a, ListNode b){
if (a == null || b == null){
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null){
if (aPtr.val < bPtr.val){
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
} |
|
mark |
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()){
return{};
}
else if (lists.size() == 1){
return lists[0];
}
int n = 1;
while (n < lists.size()){
for (int i = 0; i < lists.size() - n; i += n * 2){
lists[i] = mergeTwoLists(lists[i], lists[i + n]);
}
n *= 2;
}
return lists[0];
}
ListNode* mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *head = new ListNode();
ListNode *p = head, *p1 = l1, *p2 = l2;
while (p1 && p2) {
if (p1->val < p2->val) {
p->next = p1;
p1 = p1->next;
}
else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1 != nullptr){
p->next = p1;
}
else{
p->next = p2;
}
return head->next;
} |
思路堆排序 代码class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
minHeap = []
for x in lists:
while x:
heapq.heappush(minHeap, x.val)
x = x.next
dummy = ListNode(-1)
x = dummy
while minHeap:
x.next = ListNode(heapq.heappop(minHeap))
x = x.next
return dummy.next复杂度
|
复杂度 |
# 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:
if not lists: return
n = len(lists)
return self.merge(lists, 0, n-1)
def merge(self, lists, left, right):
if left == right:
return lists[left]
mid = left + (right - left) // 2
l1 = self.merge(lists, left, mid)
l2 = self.merge(lists, mid + 1, right)
return self.mergeTwoLists(l1, l2)
def mergeTwoLists(self, l1, l2):
if not l1: return l2
if not l2: return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2 |
|
/**
|
# 【Day 69】23. 合并 K 个排序链表代码class Solution {
private:
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
ListNode head(0), *tail = &head;
while (a && b) {
if (a->val < b->val) { tail->next = a; a = a->next; }
else { tail->next = b; b = b->next; }
tail = tail->next;
}
tail->next = a ? a : b;
return head.next;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return NULL;
for (int N = lists.size(); N > 1; N = (N + 1) / 2) {
for (int i = 0; i < N / 2; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[N - 1 - i]);
}
}
return lists[0];
}
};复杂度时间复杂度：O(KN∗LogK) 空间复杂度：O(LogK) |
|
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){ |
Understand:Plan:Evaluate:Code:class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null) return null;
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> (a.val - b.val));
ListNode dummy = new ListNode(0);
ListNode pre = dummy;
// insert non-empty heads into minHeap
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
minHeap.offer(lists[i]);
}
}
while(!minHeap.isEmpty()) {
ListNode cur = minHeap.poll();
pre.next = cur;
pre = pre.next;
if (cur.next != null) {
minHeap.offer(cur.next);
}
}
return dummy.next;
}
} |
C implementationstruct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
int i = 0, j = 0, m = 0;
struct ListNode *head = malloc(sizeof(struct ListNode)); //头结点
head->next = NULL;
struct ListNode *tail = head, *min = head;
while(1){
for(i = 0; (i < listsSize) && !lists[i]; i++){
//找到链表数组里第一个非空的元素
}
if(i < listsSize){
min = lists[i];
m = i;
}
else{ //链表全空，退出循环
break;
}
for(j=i+1; j<listsSize; j++){ //记录链表最小结点的位置
if(lists[j] && (lists[j]->val < min->val)){
min = lists[j];
m = j;
}
}
tail->next = min; //将最小结点加入head链表
tail = tail->next;
lists[m] = lists[m]->next;
}
return head->next;
} |
|
class Solution { |
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
} |
思路
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
struct cmp{
bool operator()(ListNode* & node1, ListNode* & node2)
{
return node1->val > node2->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
for(int i=0; i<lists.size(); i++)
{
if(lists[i])
pq.push(lists[i]);
}
if(pq.size()==0)
{
return NULL;
}
ListNode* start = pq.top();
ListNode* prev = NULL;
while(pq.size())
{
auto q_top = pq.top();
pq.pop();
if(prev!=NULL)
prev->next = q_top;
prev = q_top;
if(q_top->next)
{
pq.push(q_top->next);
}
}
return start;
}
};Complexity:Space:O(n) |
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
curt = dummy = ListNode(0)
q = []
count = 0
for node in lists:
if node is not None:
count += 1
heapq.heappush(q, (node.val, count, node))
while len(q) > 0:
_, _, curt.next = heapq.heappop(q)
curt = curt.next
if curt.next is not None:
count += 1
heapq.heappush(q, (curt.next.val, count, curt.next))
return dummy.nextTime Complexity: O(NlogK), Space Complexity: O(N) |
|
多个 merge two sorted list class Solution(object):
def mergeKLists(self, lists):
if not lists:
return None
if len(lists) == 1:
return lists[0]
mid = len(lists) // 2
l, r = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:])
return self.merge(l, r)
def merge(self, l, r):
dummy = p = ListNode()
while l and r:
if l.val < r.val:
p.next = l
l = l.next
else:
p.next = r
r = r.next
p = p.next
p.next = l or r
return dummy.next
def merge1(self, l, r):
if not l or not r:
return l or r
if l.val< r.val:
l.next = self.merge(l.next, r)
return l
r.next = self.merge(l, r.next)
return r |
代码
C++ Code: class Solution {
public:
struct Status {
int val;
ListNode *ptr;
bool operator < (const Status &rhs) const {
return val > rhs.val;
}
};
priority_queue <Status> q;
ListNode* mergeKLists(vector<ListNode*>& lists) {
for (auto node: lists) {
if (node) q.push({node->val, node});
}
ListNode head, *tail = &head;
while (!q.empty()) {
auto f = q.top(); q.pop();
tail->next = f.ptr;
tail = tail->next;
if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
}
return head.next;
}
};
|
代码
C++ Code: /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
struct cmp {
bool operator() (ListNode * a, ListNode * b) {
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) {
return NULL;
}
ListNode * dummy = new ListNode(-1);
ListNode * temp = dummy;
priority_queue<ListNode *, vector<ListNode *>, cmp> q;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i] != NULL) {
q.push(lists[i]);
}
}
while (!q.empty()) {
ListNode * node = q.top();
temp->next = node;
temp = temp->next;
if (node->next != NULL) {
q.push(node->next);
}
q.pop();
}
return dummy->next;
}
};复杂度分析 令 n 为数组长度。
|
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
import heapq
dummy = ListNode(val = 0)
p = dummy
h = []
for lst in lists:
head = lst
while head:
heapq.heappush(h, head.val)
head = head.next
while h:
p.next = ListNode(val = heapq.heappop(h))
p = p.next
return dummy.next |
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:return
n = len(lists)
return self.merge(lists, 0, n-1)
def merge(self,lists, left, right):
if left == right:
return lists[left]
mid = left + (right - left) // 2
l1 = self.merge(lists, left, mid)
l2 = self.merge(lists, mid+1, right)
return self.mergeTwoLists(l1, l2)
def mergeTwoLists(self,l1, l2):
if not l1:return l2
if not l2:return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2 |
Note
Solution# 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[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode()
prev = dummy
q = []
for idx, n in enumerate(lists):
if n:
heapq.heappush(q, (n.val, idx, n))
while q:
_, idx, n = heapq.heappop(q)
if n.next:
heapq.heappush(q, (n.next.val, idx, n.next))
prev.next = n
prev = n
return dummy.nextTime complexity: O(NlogK) N is the total number of nodes. K=len(lists) Space complexity: O(K) |
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r){
if (l == r){
return lists[l];
}
if (l > r){
return null;
}
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode mergeTwoLists(ListNode a, ListNode b){
if (a == null || b == null){
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null){
if (aPtr.val < bPtr.val){
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
}复杂度分析:时间复杂度:O(N) |
1 similar comment
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r){
if (l == r){
return lists[l];
}
if (l > r){
return null;
}
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode mergeTwoLists(ListNode a, ListNode b){
if (a == null || b == null){
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null){
if (aPtr.val < bPtr.val){
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
}复杂度分析:时间复杂度:O(N) |
代码class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode()
prev = dummy
q = []
for idx, n in enumerate(lists):
if n:
heapq.heappush(q, (n.val, idx, n))
while q:
_, idx, n = heapq.heappop(q)
if n.next:
heapq.heappush(q, (n.next.val, idx, n.next))
prev.next = n
prev = n
return dummy.next |
思考分治，参考mergesort 关键点复杂度分析 代码(Python)class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def mergeTwo(l1: ListNode, l2: ListNode) -> ListNode:
if l2 is None: return l1
dummy = ListNode()
curr = dummy
while l1 is not None and l2 is not None:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr= curr.next
while l1 is not None:
curr.next = l1
l1 = l1.next
curr= curr.next
while l2 is not None:
curr.next = l2
l2 = l2.next
curr= curr.next
return dummy.next
if len(lists)==0: return None
elif len(lists)==1: return lists[0]
else:
merges = []
for i in range(0,len(lists),2):
head1 = lists[i]
head2 = lists[i+1] if i+1<len(lists) else None
merged = mergeTwo(head1, head2)
merges.append(merged)
return self.mergeKLists(merges)复杂度分析
|
|
ListNode* mergeTwoLists(ListNode *a, ListNode *b) { |
代码
C++ Code: /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* merge2Lists(ListNode* l, ListNode* r)
{
if(!l)
return r;
if(!r)
return l;
ListNode* idx = new ListNode();
ListNode* head = idx;
while(l&&r)
{
if(l->val<r->val)
{
idx->next = l;
l = l->next;
}
else
{
idx->next = r;
r = r->next;
}
idx = idx->next;
idx->next = nullptr;
}
while(l)
{
idx->next = l;
l = l->next;
idx = idx->next;
idx->next = nullptr;
}
while(r)
{
idx->next = r;
r = r->next;
idx = idx->next;
idx->next = nullptr;
}
return head->next;
}
ListNode* merge(vector<ListNode*>& lists,int l,int r)
{
if(l==r)
return lists[l];
if(l>r)
return nullptr;
int mid = (l+r)>>1;
return merge2Lists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists,0,lists.size()-1);
}
};
|
|
Similar to the mergeSort, we need to first split all numdo a merge # 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:
if len(lists) == 0:
return None
if len(lists) == 1:
return lists[0]
N = len(lists)
left = self.mergeKLists(lists[:N//2])
right = self.mergeKLists(lists[N//2:])
return self.merge(left, right)
def merge(self, left, right):
if not left:
return right
if not right:
return left
dummy = ListNode(0)
prev = dummy
while left and right:
if left.val < right.val:
prev.next = left
left = left.next
else:
prev.next = right
right = right.next
prev = prev.next
if not left:
prev.next = right
else:
prev.next = left
return dummy.next
Maximal length of a subarray: M |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
23. 合并 K 个排序链表
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/merge-k-sorted-lists/
前置知识
题目描述
The text was updated successfully, but these errors were encountered: