leetcode链表反转（递归）总结——全部翻转，部分反转

参考：

由于链表反转使用迭代的思路进行实现比较简单，只是写法上比较复杂，所以这里仅整理记录一下递归反转链表的解法

一.全部反转

1.1 题目

使用递归反转链表，并返回链表

1.2 解法

/**
     * 递归反转链表
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
          
   
        if(head.next == null){
          
   
            return head;
        }
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last ;
    }

1.3 算法过程详解

1）递归操作（这里就是进行递归的地方）

ListNode last = reverseList(head.next);

函数的传入值：后置链表（head后面的链表） 函数的作用：将后置链表进行反转 函数的返回值：返回反转之后的第一个节点（也就是反转之前的最后一个节点）

假设我们想反转这个链表： 那么执行完这一步之后，已经变成了这个样子：

此时head指向1，last 指向6，后置链表已经全部反转 之后我们就要开始将1也开始加入反转链表中

2）反转操作

第一行代码是让2的next指向1 第二行的代码是让1的next指向null 此时就已经完成了整个链表的反转

head.next.next = head;
    head.next = null;

完成上述操作后，该链表已经变成这样：已经完成了整个链表的反转

3）base case

当递归到最后一个节点的时候，返回该节点即可

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

至此，已经完成了链表反转操作，实际上这个函数会一直递归到倒数第二个节点，中间的反转操作会在倒数第二个节点开始进行操作，直到递归到第一个节点，中间的每一个节点都会进行反向操作，这也就是我之前说的为什么反向操作是最核心的地方。

二. 反转前n个节点

2.1 解法

/**
 * 递归反转前n个节点
 * @return
 */
ListNode successor;
public ListNode reverseListN(ListNode head, int n) {
          
   
    if(n == 1){
          
   
        successor= head.next;
        return head;
    }

    ListNode last = reverseListN(head.next,n-1);
    head.next.next = head;
    head.next = successor;
    return last;

}

2.2 算法过程详解

实际上反转前n个链表节点跟反转全部节点区别仅仅在于base case和最后连接整个链表的操作。 这个n的意义仅仅是判断是否到达了最后一个要反转的链表节点，也就是base case的判断条件点

reverseListN(head.next,n)

整个大方法的作用就是将前n个链表节点反转，并返回第n个节点指针

1）递归

ListNode last = reverseListN(head.next,n-1);

方法返回last指向的就是第n个节点

2）操作

反转操作，将该节点也加入反转

head.next.next = head;

3）base case

if(n == 1){
          
   
        successor= head.next;
        return head;
    }

这里的successor指向的是第n+1个节点，因为将前n个节点反转之后，还需要将后面的节点连起来，所以需要记录

4）连接链表

head.next = successor;

三. 反转部分链表

3.1 题目

3.2 思路

如果上面的链表看懂了，其实反转部分链表就非常简单了，因为只需要定位到需要反转链表的第一个节点，再使用反转前n- m个节点的方法就可以完成操作

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;
}