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