链表——递归魔法：反转单链表

一、递归反转整个链表

力扣第 206 题「 反转链表」

迭代：

class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode pre=head;
        ListNode post=null;
        while(pre!=null){
            head=pre;
            pre=pre.next;
            head.next=post;
            post=head;
        }

        return head;
    }
    
}

递归：

// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

详细解释一下这段代码。

对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverse 函数定义是这样的：

输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

明白了函数的定义，再来看这个问题。比如说我们想反转这个链表：

那么输入 reverse(head) 后，会在这里进行递归：

ListNode last = reverse(head.next);

不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：

这个 reverse(head.next) 执行完成后，整个链表就成了这样：

并且根据函数定义，reverse 函数会返回反转之后的头结点，我们用变量 last 接收了。

现在再来看下面的代码：

head.next.next = head;
head.next = null;
return last;

这样整个链表就反转过来了！递归代码就是这么简洁优雅，不过其中有两个地方需要注意：

1. 递归函数要有 base case，也就是这句：

if (head == null || head.next == null) {
    return head;
}

2. 当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null：

二、反转链表前 N 个节点

这次我们实现一个这样的函数：

// 将链表的前 n 个节点反转（n <= 链表长度）
ListNode reverseN(ListNode head, int n)

比如说对于下图链表，执行 reverseN(head, 3)：
解决思路和反转整个链表差不多，只要稍加修改即可：

ListNode successor=null
ListNode reverseN(ListNode head, int n) {
    if (n==1) {
        successor=head.next;
        return head;
    }
    ListNode last = reverseN(head.next,n-1);
    head.next.next = head;
    head.next = successor;
    return last;
}

三、反转链表的一部分

力扣第 92 题「 反转链表 II」：

给一个索引区间 [m, n]（索引从 1 开始），仅仅反转区间中的链表元素。

首先，如果 m == 1，就相当于反转链表开头的 n 个元素嘛，也就是我们刚才实现的功能：

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        // 相当于反转前 n 个元素
        return reverseN(head, n);
    }
    // ...
}

那么我们只需要移动m到1就可以复用之前的代码了

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

25. K 个一组翻转链表

leecode 【25. K 个一组翻转链表】

看到k个一组，就应该联想到上面那道题，先翻转k个，然后向后移动k个，然后再翻转，但需要注意的是前后断链处的处理：

完整代码：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
            // 不足 k 个，不需要反转，base case
            if (b == null) return head;
            b = b.next;
        }
        ListNode newHead=re(a,b);
        a.next=reverseKGroup(b,k);
        return newHead;
    }
    //  [head,tail)左闭右开
    public ListNode re(ListNode head,ListNode tail){
        ListNode pre=null,cur=head,next=head;
        while(cur!=tail){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}