【Day 87 】2021-12-05 - 23.合并 K 个排序链表 #106
Comments
思路:根据题意, 有点归并、分治的感觉, 可以用堆排序来做。 方法: 堆排序借助priority_queue, 使用node的val构造一个小顶堆。 代码:实现语言: C++ class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty())
return nullptr;
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 != nullptr)
{
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 != nullptr) /* 只要挂接点后面还有结点，则将其压入栈，继续从中拿出最小值，循环往复 */
{
nodesQ.push(cur->next);
}
}
return fakeHead->next;
}
};复杂度分析:
|
let numsArr = [];
lists.forEach(item => {
while(item && item.val !== null) {
numsArr.push(item.val);
item = item.next;
}
});
numsArr = numsArr.sort((a, b) => b - a);
let resultNode = null;
numsArr.forEach(item => {
let tempNode = new ListNode(item);
tempNode.next = resultNode;
resultNode = tempNode;
})
return resultNode; |
# 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:
lenth = len(lists)
# basic cases
if lenth == 0: return None
if lenth == 1: return lists[0]
if lenth == 2: return self.mergeTwoLists(lists[0], lists[1])
# divide and conqure if not basic cases
mid = lenth // 2
return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:lenth]))
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ListNode(0)
c1, c2, c3 = l1, l2, res
while c1 or c2:
if c1 and c2:
if c1.val < c2.val:
c3.next = ListNode(c1.val)
c1 = c1.next
else:
c3.next = ListNode(c2.val)
c2 = c2.next
c3 = c3.next
elif c1:
c3.next = c1
break
else:
c3.next = c2
break
return res.next |
|
思路：堆排序 时间复杂度: O(NlogN) |
解题思路堆。多路归并问题。建立小顶堆来储存所有非空链表的头节点。建立一个dummy节点来合并链表。每次从小顶堆取值最小的头节点，然后连到合并链表的尾部，之后更新头节点和链表尾部，如果头节点不是null，则放入堆中。如此循环直到堆为空。最后返回合并好的链表的头节点dummy.next即可。 代码class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// use min-heap to store the head nodes from the k linked-list, sorted by value of the node
PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
// put nodes in heap
for (ListNode list : lists) {
// only put non-empty list in the heap
if (list != null) heap.offer(list);
}
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (!heap.isEmpty()) {
// get the head with smallest value and connect to the tail of merged list
ListNode head = heap.poll();
cur.next = head;
cur = cur.next;
// update head to the list and put a new head into heap if the new head is not null
head = head.next;
if (head != null) heap.offer(head);
}
return dummy.next;
}
}复杂度分析
|
|
思路
Java Code public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val);
ListNode dummy = new ListNode(0);
for (ListNode node : lists) {
if (node != null) {
pq.add(node);
}
}
ListNode p = dummy;
while (!pq.isEmpty()) {
ListNode cur = pq.poll();
p.next = cur;
p = p.next;
if (cur.next != null) {
pq.add(cur.next);
}
}
return dummy.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:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto comp = [](ListNode* & node1, ListNode* & node2 ) {return node1->val> node2->val;};
priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp);
for(int i=0;i < lists.size(); i++)
{
if(lists[i])
pq.push(lists[i]);
}
ListNode* prev = NULL;
ListNode* ret = NULL;
while(pq.size())
{
ListNode* topNode = pq.top();
pq.pop();
if(prev == NULL)
ret = topNode;
else
prev->next = topNode;
if(topNode->next)
pq.push(topNode->next);
prev = topNode;
}
return ret;
}
};
|
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[r];
}
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 l1, ListNode l2){
// if (l1 == null || l2 == null) {
// return l1 != null ? l1 : l2;
// }
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
ListNode aPtr = l1, bPtr = l2;
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;
}
if (aPtr != null){
tail.next = aPtr;
} else {
tail.next = bPtr;
}
return dummy.next;
}
} |
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> heap = new PriorityQueue<>(lists.length, (n1, n2) -> {
if (n1.val > n2.val) {
return 1;
} else {
return -1;
}
});
for (int i = 0; i < lists.length; ++i) {
if (lists[i] != null)
heap.offer(lists[i]);
}
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (!heap.isEmpty()) {
ListNode node = heap.poll();
cur.next = node;
if (node.next != null) {
heap.offer(node.next);
}
cur = cur.next;
}
return dummy.next;
}
} |
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) |
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
curt = dummy = ListNode(0)
heap = []
count = 0
for node in lists:
if node is not None:
count += 1
heapq.heappush(heap, (node.val, count, node))
while len(heap) > 0:
_, _, curt.next = heapq.heappop(heap)
curt = curt.next
if curt.next is not None:
count += 1
heapq.heappush(heap, (curt.next.val, count, curt.next))
return dummy.nextTime Complexity: O(nlogn), Space Complexity: O(n) |
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
memo = {idx: x for idx, x in enumerate(lists)}
q = [[x.val, idx] for idx, x in enumerate(lists) if x]
heapify(q)
cur = dummy = ListNode(0)
while q:
_, idx = heappop(q)
node = memo[idx]
cur.next = node
if node.next:
heappush(q, [node.next.val, idx])
memo[idx] = node.next
cur = cur.next
return dummy.next |
|
heap class Solution(object):
def mergeKLists(self, lists):
import heapq
dummy = ListNode(0)
p = dummy
head = []
for i in range(len(lists)):
if lists[i] :
# print lists[i].val, i
heapq.heappush(head, (lists[i].val, i))
# print head
lists[i] = lists[i].next
while head:
val, idx = heapq.heappop(head)
# print head
p.next = ListNode(val)
p = p.next
if lists[idx]:
# print idx, lists[idx]
heapq.heappush(head, (lists[idx].val, idx))
# print head
lists[idx] = lists[idx].next
return dummy.nextT: O(NlogK) N is the total num of all nodes, K is the num of lists |
23. Merge k Sorted ListsIntuition
Code/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
const mergeKLists = function(lists) {
const dummy = new ListNode(0);
let current = dummy;
const minHeap = new BinaryHeap((c, p) => c.val > p.val);
for (const head of lists) {
if (head) minHeap.push(head);
}
while (minHeap.size() > 0) {
const minNode = minHeap.pop();
current.next = minNode;
current = current.next;
if (minNode.next) minHeap.push(minNode.next);
}
return dummy.next;
};Complexity Analysis
|
思路分治。 代码(C++)class Solution {
public:
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
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 mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
};复杂度分析
|
Idea:Heap 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
heap = []
for i in range(len(lists)):
if lists[i]:
heapq.heappush(heap, (lists[i].val, i, lists[i]))
head = ListNode(0)
dummy = head
while heap:
_, i, dummy.next = heapq.heappop(heap)
dummy = dummy.next
if dummy.next:
heapq.heappush(heap, (dummy.next.val, i, dummy.next))
return head.nextComplexity:Time: O(N log K) |
Idea:divide and conquer Complexity:Time: O(Nlogk). /**
* 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.length == 0)
return null;
if(lists.length==1)
return lists[0];
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 left = mergeSort(lists, start, mid);
ListNode right = mergeSort(lists, mid+1, end);
ListNode dummy = new ListNode(-1), tail = dummy;
while(left != null || right != null) {
int val1 = (left==null? Integer.MAX_VALUE:left.val);
int val2 = (right == null? Integer.MAX_VALUE: right.val);
if(val1<val2) {
tail.next= left;
left = left.next;
}
else {
tail.next = right;
right=right.next;
}
tail= tail.next;
}
return dummy.next;
}
} |
|
基本思路 Divide & conquer, 不断两两合并 代码 复杂度分析 Time complexity: O(NlogK) 假设 K: num of lists, N 两list 总数, merge 两个list 时间复杂度为 O (N) Space complexity: O(1) |
Problem 23. Merge k Sorted ListsAlgorithm
Complexity
CodeLanguage: Java public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
merge(lists, 0, lists.length - 1);
return lists[0];
}
private void merge(ListNode[] lists, int left, int right) {
// Merge lists from index left to right, and save merged list to index left
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
merge(lists, left, mid);
merge(lists, mid + 1, right);
// Merge the two lists on left and mid + 1
ListNode dummy = new ListNode();
ListNode cur = dummy;
ListNode l1 = lists[left];
ListNode l2 = lists[mid + 1];
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
// Handle remaining of 1l or l2 and attach to the merged list
if (l1 != null) {
cur.next = l1;
}
if (l2 != null) {
cur.next = l2;
}
// Set the merged list to index left
lists[left] = dummy.next;
} |
func mergeKLists(lists []*ListNode) *ListNode {
n := len(lists)
if n == 0{
return nil
}
if n == 1{
return lists[0]
}
mid := n>>1
return merge(mergeKLists(lists[:mid]),mergeKLists(lists[mid:]))
}
func merge(l1 *ListNode,l2 *ListNode) *ListNode{
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil{
if l1.Val < l2.Val{
cur.Next = l1
l1 = l1.Next
}else{
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
if l1 != nil{
cur.Next = l1
}
if l2 != nil{
cur.Next = l2
}
return dummy.Next
} |
思路先把每个 list 中的第一个节点的值以及节点的 index 加入堆中 用一个哨兵节点当 head, 然后每次从堆中取出最小的节点与 head 相连接 如果这个节点有下一个节点, 那么将下一个节点的值和节点 index 继续加入堆中 最后返回哨兵节点 head 的下一个节点 head.next 是新链表的开头 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def __lt__(self, other):
return self.val < other.val
ListNode.__lt__ == __lt__
print(ListNode.__lt__)
h = []
for node in lists:
if node is not None:
h.append(node)
heapq.heapify(h)
# dummy node
head = ListNode()
cur = head
while h:
node = heapq.heappop(h)
cur.next = node
cur = node
if node.next is not None:
heapq.heappush(h, node.next)
return head.next复杂度时间复杂度: O(kn logk) heap 的大小最大为 k, 插入删除都是 O(logk), 最多有 kn 个点, 每个都被插入删除一次, 时间复杂度为 O(kn logk) 空间复杂度: 堆的空间复杂度为 O(k) |
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0)
return null;
ListNode merged = null;
for (ListNode head : lists) {
merged = mergeTwoLists(merged, head);
}
return merged;
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}只会暴力解... |
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if len(lists) == 0:
return None
heap = []
dummy = ListNode()
cur = dummy
# create k head heaps
for i in range(len(lists)):
if not lists[i]:
continue
heapq.heappush(heap,[lists[i].val,i])
lists[i] = lists[i].next
# add new element
while heap:
[node, idx] = heapq.heappop(heap)
cur.next = ListNode(node)
cur = cur.next
if lists[idx]:
heapq.heappush(heap,[lists[idx].val,idx])
lists[idx] = lists[idx].next
return dummy.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;
}
}复杂度时间复杂度: O(kn logk) 空间复杂度: O(logk) |
idea初始化：把每个list里面的链表第一个节点放堆里面。 codecomplexity时间复杂度：O(kn*log(k))， n 是所有链表中元素的总和，k 是链表个数。 空间复杂度：优先队列中的元素不超过 k 个，故渐进空间复杂度为 O(k) |
23. 合并K个升序链表// 12-5 cpp
class Solution
{
public:
ListNode* merge(ListNode * list1, ListNode * list2)
{
if (!list1)
return list2;
if (!list2)
return list1;
if (list1->val <= list2->val)
{
list1->next = merge(list1->next, list2);
return list1;
}
else
{
list2->next = merge(list1, list2->next);
return list2;
}
}
ListNode* mergeKLists(vector<ListNode *> &lists)
{
if (lists.size() == 0)
return nullptr;
ListNode *head = lists[0];
for (int i = 1; i < lists.size(); i++)
{
if (lists[i])
head = merge(head, lists[i]);
}
return head;
}
}; |
|
思路 实现语言: C++
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty())
return nullptr;
ListNode *res;
//重定义比较方式
auto cmp = [](ListNode* n1, ListNode* n2)
{
return n1->val>n2->val;
}
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> k(cmp);
for (auto& list : lists)
{
if (list != nullptr)
{
k.push(list);
}
}
ListNode* fakeHead = new ListNode(-1); /* 创建虚拟头结点 */
ListNode* cur = fakeHead;
while (!k.empty())
{
cur->next = k.top();
cur = cur->next;
k.pop();
if (cur->next != nullptr)
{
k.push(cur->next);
}
}
return fakeHead->next;
}
};复杂度分析 |
Problemhttps://leetcode.com/problems/merge-k-sorted-lists/ Notes
Solution/**
* 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> q = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
ListNode dummy = new ListNode();
ListNode tail = dummy;
for(ListNode node: lists){
if(node != null){
q.offer(node);
}
}
while(!q.isEmpty()){
ListNode cur = q.poll();
tail.next = cur;
tail = tail.next;
if(cur.next != null){
q.offer(cur.next);
}
}
return dummy.next;
}
}Complexity
|
|
/**
|
思路min heap 代码/**
* 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 comp {
public:
bool operator() (ListNode * a, ListNode * b) {
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, comp> pq;
// push all the heads in the lists
for (ListNode* node: lists) {
if (node) {
pq.push(node);
}
}
ListNode* dummyHead = new ListNode(-1);
ListNode* temp = dummyHead;
while (!pq.empty()) {
ListNode* curr = pq.top();
pq.pop();
temp->next = curr;
temp = temp->next;
// check the remaining
if (curr->next) {
pq.push(curr->next);
}
}
return dummyHead->next;
}
};时间复杂度 O(nklogk) n is the number of nodes, k is the number of lists空间复杂度 O(k) |
思路堆排序 代码class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def __lt__(self,other):
return self.val < other.val
ListNode.__lt__ = __lt__
heap = []
for i in lists:
if i :heapq.heappush(heap,i)
d = c = ListNode(-1)
while heap:
n = heapq.heappop(heap)
c.next = n
c = c.next
n = n.next
if n:heapq.heappush(heap,n)
return d.next复杂度
|
|
const merge = function (list1: ListNode, list2: ListNode): ListNode {
let head: ListNode = new ListNode(0);
let dummyHead: ListNode = head;
while (list1 && list2) {
if (list1.val < list2.val) {
dummyHead.next = list1;
list1 = list1.next;
} else {
dummyHead.next = list2;
list2 = list2.next;
}
dummyHead = dummyHead.next;
}
if (list1) dummyHead.next = list1;
if (list2) dummyHead.next = list2;
return head.next;
};
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
let len: number = lists.length;
if (len === 0) return null;
if (len < 2) return lists[0];
let mid = Math.floor(len / 2);
let left = mergeKLists(lists.slice(0, mid));
let right = mergeKLists(lists.slice(mid));
return merge(left, right);
} |
题目https://leetcode-cn.com/problems/merge-k-sorted-lists/ 思路Heap python3# 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:
# time nlogn
# space n
# heapq
# 遍历lists加入所有node的值 python默认最小堆直接弹出后串起来即可
heap = []
for node in lists:
while node:
heapq.heappush(heap, node.val)
node = node.next
dummy = ListNode(0, None)
cur = dummy
while heap:
Val = heapq.heappop(heap)
cur.next = ListNode(Val, None)
cur = cur.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:
# time nlogn
# space n
heap = []
# for i, node in enumerate(lists):
# if node:
# heapq.heappush(heap, (node.val, i))
for i in range(0, len(lists)):
if lists[i]:
heapq.heappush(heap, (lists[i].val, i))
if not heap: return None
dummy = ListNode(0, None)
cur = dummy
while heap:
val, idx = heapq.heappop(heap)
cur.next = ListNode(val, None)
cur = cur.next
lists[idx] = lists[idx].next
if lists[idx]:
heapq.heappush(heap, (lists[idx].val, idx))
return dummy.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; }
* }
*/
//整体思路：基于合并两个排序链表的方法，延伸为合并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)/2;
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);//这里不能定义为null，null节点就没有next等属性用来操作了
ListNode curr=head;
ListNode aPtr=a;
ListNode bPtr=b;
while(aPtr!=null&&bPtr!=null){
if(aPtr.val<bPtr.val){
curr.next=aPtr;
aPtr=aPtr.next;
}
else{
curr.next=bPtr;
bPtr=bPtr.next;
}
curr=curr.next;
}
curr.next=aPtr!=null?aPtr:bPtr;
return head.next;
}
} |
|
title: "Day 87 23. 合并K个升序链表" 23. 合并K个升序链表题目给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4题目思路
/**
* 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* mergeKLists(vector<ListNode*>& lists) {
auto min = [](ListNode *a, ListNode *b)
{
return a -> val > b -> val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(min)> ans(min);
auto *root = new ListNode();
for(auto p: lists)
{
if(p != nullptr) ans.push(p);
}
ListNode *cur = root;
while(!ans.empty())
{
ListNode *tmp = ans.top(); ans.pop();
if(tmp -> next != nullptr) ans.push(tmp->next);
tmp -> next = cur -> next;
cur -> next = tmp;
cur = cur -> next;
}
return root -> next;
}
};复杂度
|
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def mergeTwoLists(root1, root2):
n1 = root1
n2 = root2
tempHead = ListNode(0)
head = tempHead
while (n1 != None and n2 != None):
if n1.val < n2.val:
tempHead.next = n1
n1 = n1.next
else:
tempHead.next = n2
n2 = n2.next
tempHead = tempHead.next
tempHead.next = n1 if n2 == None else n2
return head.next
if not lists:
return None
if len(lists) <= 1:
return lists[0]
merged = mergeTwoLists(lists[0], lists[1])
for i in range(2, len(lists)):
merged = mergeTwoLists(merged, lists[i])
return merged
|
Complexity Analysis
|
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;
} |
【day87】题目地址（23. 合并 K 个排序链表）与69日分治板块题相同https://leetcode-cn.com/problems/merge-k-sorted-lists/ 采用python小顶堆做：加入所有Node ,一个个输出即可 # 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 list1 in lists:
while list1:
heapq.heappush(heap, list1.val)
list1 = list1.next
dummy = ListNode(0, None)
cur = dummy
while heap:
VALUE = heapq.heappop(heap)
cur.next = ListNode(VALUE, None)
cur = cur.next
return dummy.next复杂度分析： 时间复杂度：O(knlogn) 堆中的元素不超过K个，n个链表，每个元素的偶被插入删除一次logn 空间复杂度：O（k） |
【Day 87】23.合并 K 个排序链表代码/**
* 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 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;
}
}; |
代码class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
tmp = ListNode(-1)
x = tmp
tmp2 = []
for i in lists:
p = i
while p != None:
tmp2.append(p.val)
p = p.next
tmp2.sort()
for i in tmp2:
k = ListNode(i)
x.next = k
x = x.next
return tmp.next |
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;
} |
思路老题了，归并分治做法，一会儿再试试堆的做法，复杂度是nklogk 代码 def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if len(lists) == 0:
return None
elif len(lists) == 1:
return lists[0]
elif len(lists) == 2:
left = lists[0]
right = lists[1]
ans = ListNode()
p = ans
while left and right:
if left.val <= right.val:
p.next = left
left = left.next
else:
p.next = right
right = right.next
p = p.next
p.next = left if left else right
return ans.next
else:
n = len(lists)
return self.mergeKLists([self.mergeKLists(lists[:n // 2]), self.mergeKLists(lists[n // 2:])]) |
JAVA版本直接使用了堆排序。
时间复杂度：O(nlogn)空间复杂度：O(n） |
思路
代码javascript /*
* @lc app=leetcode.cn id=23 lang=javascript
*
* [23] 合并K个升序链表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
const heap = new minHeap()
const dummyHead = new ListNode()
let cur = dummyHead
for (const list of lists) {
if (!list) continue
heap.enqueue(list, list.val)
}
while (!heap.isEmpty()) {
let node = heap.dequeue()
cur.next = node
cur = cur.next
node.next && heap.enqueue(node.next, node.next.val)
}
return dummyHead.next
};
// @lc code=end复杂度分析
|
var mergeKLists = function (lists) {
const list = [];
for (let i = 0; i < lists.length; i++) {
let node = lists[i];
while (node) {
list.push(node.val);
node = node.next;
}
}
list.sort((a, b) => a - b);
const res = new ListNode();
let now = res;
for (let i = 0; i < list.length; i++) {
now.next = new ListNode(list[i]);
now = now.next;
}
return res.next;
}; |
|
class Solution { |
代码
C++ Code: 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);
}
};
|
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) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b)->(a.val - b.val));
for (ListNode list : lists) {
if (list != null) {
minHeap.add(list);
}
}
while (!minHeap.isEmpty()) {
ListNode curNode = minHeap.poll();
cur.next = curNode;
cur = cur.next;
if (curNode.next != null) {
minHeap.offer(curNode.next);
}
}
return dummy.next;
}
} |
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
ListNode res = null;
for (int i = 0; i < lists.length; i++)
res = mergeTwoLists(res, lists[i]);
return res;
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null)
return l1 == null ? l2 : l1;
ListNode fakehead = new ListNode(0), tmp = fakehead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
fakehead.next = l1;
l1 = l1.next;
} else {
fakehead.next = l2;
l2 = l2.next;
}
fakehead = fakehead.next;
}
fakehead.next = l1 != null ? l1 : l2;
return tmp.next;
}
} |
|
class Solution { } |
代码class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0) {
return null;
}
return merge(lists, 0, lists.length - 1);
}
public ListNode merge (ListNode[] lists, int lo, int high) {
if(lo == high) {
return lists[lo];
}
int mid = lo + (high - lo) / 2;
ListNode l1 = merge(lists, lo, mid);
ListNode l2 = merge(lists, mid + 1, high);
return merge2Lists(l1, l2);
}
public ListNode merge2Lists(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
ListNode newList = null;
if(l1.val < l2.val){
newList = l1;
newList.next = merge2Lists(l1.next, l2);
} else {
newList = l2;
newList.next = merge2Lists(l1, l2.next);
}
return newList;
}
} |
Note优先队列，小顶堆 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;
}
ListNode cur = lists[0];
ListNode pre = new ListNode(0, cur);// 哑节点
int n = lists.length;
PriorityQueue<ListNode> queue =
new PriorityQueue<>((a, b) -> ((ListNode)a).val - ((ListNode)b).val);
if (cur == null) {
boolean empty = true;
for(int i = 1; i < n; i++) {
if (lists[i] != null) {
lists[0] = cur = lists[i];
lists[i] = null;
empty = false;
break;
}
}
if (empty) {
return null;
}
}
ListNode ans = lists[0];
while (cur != null) {
for (int i = 1; i < n; i++) {
while (lists[i] != null && lists[i].val <= cur.val) {
queue.add(lists[i]);
lists[i] = lists[i].next;
}
}
if (cur == lists[0] && queue.size() != 0) {
ans = queue.peek();
}
while (queue.size() != 0) {
ListNode add = queue.remove();
pre.next = add;
add.next = cur;
pre = add;
}
pre = cur;
cur = cur.next;
}
for (int i = 1; i < n; i++) {
while (lists[i] != null) {
queue.add(lists[i]);
lists[i] = lists[i].next;
}
}
while (queue.size() != 0) {
ListNode add = queue.remove();
pre.next = add;
add.next = cur;
pre = add;
}
return ans;
}
}Complexity
|
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);
}; |
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty())
return nullptr;
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 != nullptr)
{
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 != nullptr) /* 只要挂接点后面还有结点，则将其压入栈，继续从中拿出最小值，循环往复 */
{
nodesQ.push(cur->next);
}
}
return fakeHead->next;
}
};``` |
思路1 - PQ
Java Code public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
List<Integer> countList = new ArrayList<>();
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> matrix[a[0]][a[1]]));
for (int i = 0; i < n; i++) {
pq.add(new int[]{i, 0});
}
while (countList.size() != k) {
int[] cur = pq.poll();
int x = cur[0], y = cur[1];
countList.add(matrix[x][y]);
if (y + 1 < n) {
pq.add(new int[]{x, y + 1});
}
}
return countList.get(k - 1);
}思路2 - 二分搜值
Java Codeclass Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int l = matrix[0][0], r = matrix[n - 1][n - 1];
while (l <= r) {
int m = l + (r - l) / 2;
if (count(matrix, m) < k) {
l = m + 1;
} else {
r = m - 1;
}
}
if (count(matrix, r) == k) {
return r;
} else {
return l;
}
}
private int count(int[][] matrix, int key) {
int n = matrix.length;
int x = n - 1, y = 0, count = 0;
while (x >= 0 && y < n) {
if (matrix[x][y] > key) {
x--;
} else {
count += x + 1;
y++;
}
}
return count;
}
} |
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: