10.k个链表反转

• 2.11
  • 需要哨兵放置头结点会变
  • while 的最后需要重置 pre 和 end 的指针
  • while 里的 for 循环逻辑每次让end 走 k 步（需要判断是否是 null 以提前返回）
  • start 会变成 end 的位置（java 内是引用）

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end =dummy;
        while(end.next!=null){
            for(int i=0;i<k&&end!=null;i++){
                end = end.next;
            }
            if(end==null) break;
            ListNode start = pre.next;
            ListNode tempNode = end.next;
 
            end.next = null;
 
            pre.next = reverse(start);
 
            start.next  = tempNode;
 
            pre = start;
            end = pre;
 
        }
        return dummy.next;
    }
    public ListNode reverse(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

• 1.24
  • 因为头结点会变，加哨兵节点
  • 声明 pre 和 end，while for end 的位置（判断是否合法 ）
  • 记录 start 和 nextTemp 断开后反转接上

 
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1. 设置哨兵节点，专门用来应对头节点改变的情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // pre 指向每次待翻转区域的前一个节点
        ListNode pre = dummy;
        ListNode end = dummy;
 
        while (end.next != null) {
            // 2. 让 end 走 k 步，找到这组的尾巴
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            // 如果 end 为 null，说明剩下的节点不足 k 个，无需翻转，直接结束
            if (end == null) break;
 
            // 3. 记录关键节点
            ListNode start = pre.next; // 这组的开头
            ListNode next = end.next;  // 下一组的开头
 
            // 4. 断开链表，准备独立翻转这 k 个节点
            end.next = null;
            
            // 5. 调用反转函数，并把翻转后的新头接在 pre 后面
            pre.next = reverse(start);
 
            // 6. 重新接回大链表
            // 翻转后，start 跑到了最后，把它和后面的 next 连起来
            start.next = next;
 
            // 7. 指针后移，准备下一轮
            pre = start;
            end = pre; 
        }
        return dummy.next;
    }
 
    // 标准的翻转链表辅助函数 (你之前已经掌握的模版)
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}