反转链表，k个一组反转链表，反转链表Ⅱ

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

https://leetcode.cn/problems/reverse-linked-list/description/

迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode curr = head;
        ListNode pre = null;
        

        while (curr != null) {
            // 1. 暂存下一个节点，并声明类型
            ListNode next = curr.next; 
            
            // 2. 反转：当前节点的 next 指向前一个节点
            curr.next = pre;
            
            // 3. 指针整体向后移动一步（注意顺序：先挪 pre，再挪 curr）
            pre = curr;  // pre 来到刚才反转好的节点位置
            curr = next; // curr 走向下一个待处理的节点
        }
        
        // 4. 返回新链表的头节点
        return pre;
    }

}

 

递归

class Solution {
    public ListNode reverseList(ListNode head) {
    // 1. 终止条件：如果链表为空，或者只有一个节点，直接返回
       if (head == null || head.next == null) {
            return head;
        }
        
        // 2. 递归调用：反转以 head.next 为头节点的后续链表
        // 记住：这里的 newHead 永远是原链表的最后一个节点，它会一路被向上返回
        ListNode newHead = reverseList(head.next);
        
        // 3. 核心反转逻辑（发生在“归来”阶段）：
        // 此时 head.next 代表下一个节点。把下一个节点的 next 指向当前 head，实现局部反转
        head.next.next = head;
        
        // 4. 断开当前节点原来的向后指针，防止产生环
        head.next = null;
        
        // 5. 返回新链表的头节点
        return newHead;
    }

}

 

K 个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

流程：

1. 分组：从头数 k 个为一组，不足 k 直接停
2. 段内反转：每一组内部反转
3. 接链：把反转后的段头接到前驱、段尾接下一组头

使用虚拟头节点 dummy确保头节点没变

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        while (true) {
            ListNode tail = pre;
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                if (tail == null) return dummy.next;
            }
            ListNode nextGroup = tail.next;
            ListNode newHead = reverseK(pre.next, nextGroup, k);  // 调用递归版
            ListNode newTail = pre.next;
            pre.next = newHead;
            pre = newTail;
        }
    }

    // 递归
    private ListNode reverseK(ListNode start, ListNode after, int k) {
        if (k == 1) {
            start.next = after;
            return start;
        }
        ListNode newHead = reverseK(start.next, after, k - 1);
        start.next.next = start;
        start.next = after;
        return newHead;
    }
}

反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

区间反转 = 把区间起点挪到链头 + 反转前 N 个节点，递归负责 “挪”，reverse 负责 “反转”。

① reverse(head, n)：反转前 n 个节点，返回新头

• 递归到底（n==1）时，head 是区间最后一个节点，记下它右边那个节点 s（successor）；
• 回溯时 head.next.next = head 让后继指回自己，head.next = s 把原头（变尾巴）接回右半段。

② reverseBetween(head, left, right)：把区间往前挪

• left == 1：区间起点就是链头 → 交给 reverse(head, right)，必须 return；
• left > 1：跳过 head，递归处理 head.next，区间整体 left-1, right-1，再把返回的新头接到 head.next。

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    // successor：记录反转区间右侧第一个节点（用于反转后接回右半段）
    ListNode s;

    // 反转以 head 为头的前 n 个节点，返回新头
    public ListNode reverse(ListNode head, int n) {
        // 递归到底：head 正好是区间最后一个节点
        if (n == 1) {
            s = head.next;      // 记下第 n+1 个节点（右半段的头）
            return head;        // 区间最后一个节点成为新头
        }

        // 先递归反转后面 n-1 个
        ListNode newHead = reverse(head.next, n - 1);

        head.next.next = head;  
        head.next = s;          

        return newHead;         
    }

    // 反转链表从位置 left 到 right 的区间
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 区间起点就是链头 → 直接反转前 right 个节点
        if (left == 1) {
            return reverse(head, right);  
        }

        // 跳过当前 head，区间整体前移一格，反转完接到 head 后面
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;   
    }
}