链表-递归反转链表

反转整个链表

反转链表函数 reverse 定义：输入一个结点 head，将 以 head 为起点 的链表反转，并返回反转之后的头结点

假设需要反转链表：

递归算法基础框架：

public ListNode reverse(ListNode head) {
    ListNode last = reverse(head.next);
    return last;
}

代码 reverse(head.next);的效果是什么呢？

但是我们最终期望的结果是：

怎么才能变成最终期望的结果呢？

第一步：让 head 节点的下一个节点的 next 指针从指向 null 变成指向 head 节点

第二步：让 head 节点的 next 指针指向 null

递归算法框架：

public ListNode reverse(ListNode head) {
    ListNode last = reverse(head.next);
    // 让 head 节点的下一个节点的 next 指针从指向 null 变成指向 head 节点
    head.next.next = head;
    // 让 head 节点的 next 指针指向 null 
    head.next = null;
    return last;
}

那递归结束条件是什么呢？
如果 head 是空节点，那么肯定递归就结束了。
特别需要注意的是，如果链表只有一个节点，那么也无需进行反转，递归也可以结束
完整地递归算法：

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    // 让 head 节点的下一个节点的 next 指针从指向 null 变成指向 head 节点
    head.next.next = head;
    // 让 head 节点的 next 指针指向 null 
    head.next = null;
    return last;
}

反转链表前 N 个节点

那么如果只是想反转链表前 N 个节点呢：

// head 的后驱节点
ListNode successor = null; 
// 以 head 为起点，需要反转前 n 个节点
public ListNode reverseN(ListNode head, int n ) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);
    // 让 head 节点的下一个节点的 next 指针从指向 null 变成指向 head 节点
    head.next.next = head;
    // 让 head 节点的 next 指针指向 successor 
    head.next = successor;
    return last;
}

反转链表的一部分

那么如果只是想反转链表部分节点呢：

ListNode successor = null;
public ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == 1) {
        // 相当于反转前 n 个节点
        return reverseN(head, n);
    }
    // 前进到反转的起点
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}
// 以 head 为起点，需要反转前 n 个节点
public ListNode reverseN(ListNode head, int n ) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);
    // 让 head 节点的下一个节点的 next 指针从指向 null 变成指向 head 节点
    head.next.next = head;
    // 让 head 节点的 next 指针指向 successor 
    head.next = successor;
    return last;
}