[LC优选算法#17] 链表 | 合并 K 个升序链表 | K个⼀组翻转链表

1. 合并 K 个升序链表合并 K 个升序链表解题思路暴力O(N*K^2)一次合并两个有序链表循环操作直至所有链表合并为一个。虽然这种方法简单易想但一旦K很大时间复杂度就会特别高。一个一个链表合并过于冗余那能不能一次性合并所有链表呢答案是可以的每次选择K个链表中头节点值最小的元素加入链表即可。因为链表都是有序的因此我们考虑用堆的思想优化堆O(N*K*logK)创建一个小根堆放入所有的头节点在合并链表时每次选取堆顶元素尾插另找一个头节点放入堆中。堆为空则说明所有的链表都已被合并了。分治递归O(N*K*logK)在逐⼀⽐较时答案链表会变得越来越⻓每个跟它合并的⼩链表的元素都需要⽐较很多次才可以成功排序。因此我们也可以用分治递归的方式优化链表长度尽可能让长度相同的链表进行两两合并。//堆解法classSolution{public:typedefListNode Node;structcmp//需要提供比较逻辑{booloperator()(Node*n1,Node*n2){returnn1-valn2-val;}};ListNode*mergeKLists(vectorListNode*lists){priority_queueNode*,vectorNode*,cmpheap;//放入头节点for(autol:lists){if(l){heap.push(l);}}Node*newheadnewNode(0);Node*curnewhead;while(!heap.empty()){Node*tmpheap.top();heap.pop();cur-nexttmp;if(tmp-next){heap.push(tmp-next);}curcur-next;}Node*retnewhead-next;deletenewhead;returnret;}};//递归分治解法classSolution{public:typedefListNode Node;ListNode*mergeKLists(vectorListNode*lists){intnlists.size();if(n0)returnnullptr;if(n1)returnlists[0];returnMerge(lists,0,n-1);}Node*Merge(vectorListNode*lists,intleft,intright){if(leftright)returnlists[left];if(leftright)returnnullptr;intmid(leftright)/2;Node*n1Merge(lists,left,mid);Node*n2Merge(lists,mid1,right);returnMerge_Sort(n1,n2);}Node*Merge_Sort(Node*n1,Node*n2){if(n1nullptr)returnn2;if(n2nullptr)returnn1;Node*cur1n1;Node*cur2n2;Node*newheadnewNode(0);Node*curnewhead;while(cur1cur2){if(cur1-valcur2-val){cur-nextcur1;cur1cur1-next;}else{cur-nextcur2;cur2cur2-next;}curcur-next;}if(cur1){cur-nextcur1;}if(cur2){cur-nextcur2;}Node*retnewhead-next;deletenewhead;returnret;}};2. K个⼀组翻转链表K个⼀组翻转链表解题思路模拟链表具有单向性我们不能直接在原链表中翻转否则会丢失元素。因此采用头插法的方式解决翻转。步骤如下step1遍历链表记节点个数为nn/k计算需要翻转多少组。step2新建链表创建prevcurtmpptail五个变量对每组元素使用头插的方式放入链表将链表按K个为⼀组进⾏分组组内进⾏反转并且记录反转后的头尾结点使其可以和前、后连接起来。step3循环step2直至K组链表全部翻转连接剩余元素并返回头节点。classSolution{public:typedefListNode Node;ListNode*reverseKGroup(ListNode*head,intk){if(k1)returnhead;intnum0;for(Node*curhead;cur;curcur-next){num;}num/k;Node*newheadnewNode(0);Node*prevnewhead;Node*cur1head;Node*nexthead-next;Node*tailcur1;if(num0)returnnullptr;while(num--){intcnt0;while(cntk){Node*tmpprev-next;prev-nextcur1;cur1-nexttmp;cur1next;if(cur1){nextnext-next;}cnt;}prevtail;tailcur1;}prev-nextcur1;//链接剩余节点Node*retnewhead-next;deletenewhead;returnret;}};// 本期内容就到这里啦如果对你有帮助请三连支持我是青云我们下期见^_~