Last Updated: 2023-11-04 14:34:25 Saturday
-- TOC --
这道Hard题，有点不够Hard...
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
将多个已经排好序的singly-linked list，合并成一个返回，已排好序的singly-linked list的数量为k，是个参数。
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Constraints:
- k == lists.length
- 0 <= k <= 104
- 0 <= lists[i].length <= 500
- -104 <= lists[i][j] <= 104
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 104.
如果学过数据结构和算法，应该能够想到，此题考验的，是应用heap的算法，又快又省。
将所有的节点放在一起排个序。
由于在Python中，执行内置的sort是C的速度，因此暴力一点，反而整体的速度更快。
# 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]:
a = []
for lst in lists:
while lst:
a.append(lst)
lst = lst.next
if not a:
return None
a.sort(key=lambda x:x.val)
for i in range(len(a)-1):
a[i].next = a[i+1]
return a[0]
内置sort是C的速度！所以，在Python的提交中，好快....:)
/**
* 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) {
if(lists.empty())
return nullptr;
vector<ListNode*> slst;
slst.reserve(4096);
for(auto p: lists){
while(p){
slst.push_back(p);
p = p->next;
}
}
if(slst.empty())
return nullptr;
sort(slst.begin(),
slst.end(),
[](ListNode *a, ListNode *b)
{ return a->val < b->val; });
ListNode *h, *p;
h = p = slst[0];
for(auto it{slst.begin()+1}; it!=slst.end(); ++it)
p = p->next = *it;
p->next = nullptr; //!
return h;
}
};
static int cmp(const void *a, const void *b)
{ return (*(struct ListNode**)a)->val - (*(struct ListNode**)b)->val; }
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
if(listsSize == 0)
return NULL;
struct ListNode **slst = NULL;
int sidx = 0;
for(int i=0; i<listsSize; ++i){
struct ListNode *p = lists[i];
while(p){
if(sidx%256 == 0)
slst = realloc(slst, sizeof(char*)*(sidx/256+1)*256);
slst[sidx++] = p;
p = p->next;
}
}
if(sidx == 0)
return NULL;
qsort(slst, sidx, sizeof(char*), cmp);
struct ListNode *h, *p;
h = p = slst[0];
for(int i=1; i<sidx; ++i)
p = p->next = slst[i];
p->next = NULL;
free(slst);
return h;
}
当N远远大于k时，应用heap的算法会由明显优势。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def _heap_trickle_down(self, lst, idx=0):
n = len(lst)
while idx < n:
lidx = idx*2 + 1
if lidx < n:
midx = idx
if lst[lidx].val < lst[midx].val:
midx = lidx
ridx = lidx + 1
if ridx<n and lst[ridx].val<lst[midx].val:
midx = ridx
if idx == midx:
return
lst[idx], lst[midx] = lst[midx], lst[idx]
idx = midx
continue
return
def _heapify(self, lst):
for i in reversed(range(len(lst)//2)):
self._heap_trickle_down(lst, i)
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
nodes = [it for it in lists if it]
if not nodes:
return None
self._heapify(nodes)
head = p = ListNode()
while nodes:
p.next = p = nodes[0]
if nodes[0].next:
nodes[0] = nodes[0].next
else:
n = nodes.pop()
if nodes:
nodes[0] = n
else:
return head.next
self._heap_trickle_down(nodes)
return head.next
C++的<algorithm>库中，有一组操作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) {}
* };
*/
bool cmp(const void *a, const void *b)
{ return (*(ListNode*)a).val > (*(ListNode*)b).val; }
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<ListNode*> hp;
for(auto p: lists)
if(p)
hp.push_back(p);
if(hp.empty())
return nullptr;
make_heap(hp.begin(), hp.end(), cmp);
ListNode *h, *p, t {ListNode{}};
h = p = &t;
while(hp.size()){
pop_heap(hp.begin(), hp.end(), cmp);
p = p->next = hp.back();
hp.pop_back();
if(p->next){
hp.push_back(p->next);
push_heap(hp.begin(), hp.end(), cmp);
}
}
return h->next;
}
};
>，才能得到一个min heap。pop_heap其实是做了一次交换，将需要pop的元素放在了最后，自己取出来后，还要pop_back去掉。push_heap需要在push_back之后调用。static void siftdown(struct ListNode **h, int size, int idx){
while(idx < size){
int left = idx*2 + 1;
if(left < size){
int midx = idx;
if(h[midx]->val > h[left]->val)
midx = left;
int right = left + 1;
if(right<size && h[midx]->val>h[right]->val)
midx = right;
if(idx == midx)
return;
struct ListNode *t = h[idx];
h[idx] = h[midx];
h[midx] = t;
idx = midx;
continue; //!
}
return;
}
}
static void heapify(struct ListNode **h, int size){
for(int i=size/2-1; i>=0; --i)
siftdown(h, size, i);
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
struct ListNode **heap = malloc(sizeof(char*)*listsSize);
int hidx = 0;
for(int i=0; i<listsSize; ++i)
if(lists[i])
heap[hidx++] = lists[i];
if(hidx == 0){
free(heap);
return NULL;
}
heapify(heap, hidx);
struct ListNode h;
struct ListNode *r = &h;
while(hidx){
r = r->next = heap[0];
if(heap[0]->next)
heap[0] = heap[0]->next;
else{
if(--hidx)
heap[0] = heap[hidx];
else
break;
}
siftdown(heap, hidx, 0);
}
free(heap);
return h.next;
}
下面这段代码是我用来测试的，觉得还有点意思，就保留下来了，想想LeetCode可能就是用类似的代码在测试我们的提交。这段代码再次证明，singly-linked链表如果有一个sentinel head，生活将变得多么惬意......这段代码应该可以算作median级别的，单链表的创建，反向遍历，始终在头部插入节点。
int main(){
int data1[] = {-8,-7,-6,-3,-2,-2,0,3};
int data2[] = {-10,-6,-4,-4,-4,-2,-1,4};
int data3[] = {-10,-9,-8,-8,-6};
int data4[] = {-10,0,4};
// same as int *(dataset[])
int *dataset[] = {data1, data2, data3, data4};
int setnum = sizeof(dataset) / sizeof(int*);
int datanum[] = {sizeof(data1)/sizeof(int),
sizeof(data2)/sizeof(int),
sizeof(data3)/sizeof(int),
sizeof(data4)/sizeof(int)};
// dataset[0] is only a plain int*
printf("%zu\n", sizeof(dataset[0])/sizeof(int));
struct ListNode **data = malloc(sizeof(struct ListNode*)*setnum);
struct ListNode head; // on stack, no need to free
for(int i=0; i<setnum; ++i){
head.next = NULL;
for(int j=datanum[i]-1; j>=0; --j){
struct ListNode *t = malloc(sizeof(struct ListNode));
t->val = dataset[i][j];
t->next = head.next;
head.next = t;
}
data[i] = head.next;
}
// go
struct ListNode *r = mergeKLists(data, setnum);
while(r){
printf("%d ", r->val);
struct ListNode *p = r;
r = r->next;
free(p);
}
printf("\n");
free(data);
return 0;
}
本文链接：https://cs.pynote.net/ag/leetcode/202310262/
-- EOF --
-- MORE --