Leetcode 25,148：k个一组翻转链表，排序链表

1.题目描述题目解答这道题属于困难题实现起来较为复杂但本质上和昨天的两两反转链表是大同小异的。我们可以先进行单个组内的链表反转具体可以参考之前的题目。然后将反转好的链表作为结果返回给前面的链表的尾部。这个具体的过程比较的复杂需要我们反复地理解。这里需要一个特别注意的点就是当一个分组已经反转完毕之后这个新的链表的尾部节点就是head了而不是当前的cur因为当前的cur已经是当前链表尾部的下一个节点了cur需要作为下一个链表的头节点来继续加入下一轮递归。classSolution{publicListNodereverseKGroup(ListNodehead,intk){// 保存原始的 k 值因为后续反转操作会消耗 kinttempk;// 第一步检查剩余节点数是否够 k 个 // cur1 从头开始往后走 k-1 步看能否走到第 k 个节点ListNodecur1head;if(headnull){returnnull;// 空链表直接返回 null}while(k1){// 走 k-1 步到达当前组的最后一个节点cur1cur1.next;// 向后移动if(cur1null){// 还没走到第 k 个就走完了returnhead;// 不够 k 个节点保持原样不反转}k--;// 剩余步数减 1}// 此时 cur1 指向当前组的最后一个节点说明剩余节点够 k 个// 第二步恢复 k 值并反转当前组的 k 个节点 ktemp;// 恢复 k 为原始值因为上面被减成 1 了ListNodecurhead;// cur 指向当前节点从头开始ListNodeprenull;// pre 记录当前节点的前驱初始为 nullwhile(k0){// 反转 k 个节点ListNodenextcur.next;// ① 暂存下一个节点防止断链后丢失cur.nextpre;// ② 反转当前节点指向前驱precur;// ③ pre 前移到当前节点curnext;// ④ cur 前移到之前暂存的下一个节点k--;// 剩余要反转的节点数减 1}// 循环结束后pre 指向反转后的组头cur 指向下一组的第一个节点// head 仍然是当前组的第一个节点但现在它已经变成了组尾// 第三步递归处理剩余部分并连接 // head 是当前组的尾节点它的 next 连接到下一组递归反转后的新头head.nextreverseKGroup(cur,temp);// 第四步返回当前组反转后的新头 returnpre;// pre 就是反转后的组头}}2.题目描述这道题有很多种解法最简单的办法就是将数字从链表中提取到数组然后进行排序之后再将数据填入到链表之中。但是这道题给出了一个限制所以使用上述的方法是肯定不可以的那我们可以只针对链表来进行操作但是因为不可以额外开辟数组所以我们需要比较多的代码量。我们需要两个额外的方法分别是寻找链表的中点方法和合并两个升序链表的方法。然后使用归并排序先将链表进行多次的对半分割直到只剩下最小的单个节点然后两两一组进行排序并合成新的链表之后在向上层层递进重新组成为一个新的链表。classSolution{// 归并排序链表主函数publicListNodesortList(ListNodehead){// 递归终止条件空链表或只有一个节点已经有序直接返回if(headnull||head.nextnull){returnhead;}// ① 找链表的中点将链表一分ListNodemidfindmiddle(head);// ② 切分右半段的头就是 mid.next然后从 miListNoderightHeadmid.next;mid.nextnull;// 从中点切断左半段变为独立链表// ③ 递归分别对左右两半排序ListNodeleftsortList(head);// 左半段递归排序ListNoderightsortList(rightHead);// 右半段递归排序// ④ 合并将两个有序链表合并成一个returnmergeTwoLists(left,right);}// 找链表的中点快慢指针法publicListNodefindmiddle(ListNodehead){ListNodeslowhead;ListNodefasthead.next;// fast 先走一步这样偶数长度时 slow 停在左中点// 例如 [1,2,3,4]slow 停在 2mid.next3 就是右头while(fast!nullfast.next!null){slowslow.next;// slow 一次走一步fastfast.next.next;// fast 一次走两步}// 循环结束fast 到末尾slow 正好在中点returnslow;}// 合并两个升序链表 publicListNodemergeTwoLists(ListNodel1,ListNodel2){// dummy 是哨兵节点用来简化头部插入逻辑ListNodedummynewListNode(0);ListNodeccurdummy;// ccur 指向合并后链表的尾部初始指向哨兵// 两个链表都不为空时每次取较小的节点挂到 ccur 后面while(l1!nulll2!null){if(l1.vall2.val){ccur.nextl1;// l1 的值更小挂上 l1 的当前节点l1l1.next;// l1 指针后移}else{ccur.nextl2;// l2 的值更小或相等挂上 l2 的当前节点l2l2.next;// l2 指针后移}ccurccur.next;// ccur 后移保持在合并链表的尾部}// 有一条链表先走完了把另一条剩下的部分直接接上去if(l1!null){ccur.nextl1;// l1 还没走完剩下的全部挂上去}if(l2!null){ccur.nextl2;// l2 还没走完剩下的全部挂上去}// dummy.next 是合并后链表的真正头节点跳过哨兵returndummy.next;}}