递归魔法：反转单链表

整个链表递归反转

// 定义：输入单链表头结点，将链表反转，回到新的头结点Listnodee 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) 之后，递归将在这里进行

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

head.next.next = head;

head.next = null;return last;

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

ListNode successor = null; // 后驱节点 存储N+1节点    ListNode reverseN(ListNode head, int n) {        if(n==1){            successor = hean.next;        }        ListNode last = reverseN(successor.next, n - 1);        head.next.next = head;        head.next = successor;        return last;    }

1、base case 变为 n == 1，反转一个元素，即它本身，并记录后驱节点。

2、刚才我们直接把它拿走了 head.next 设置为 null，因为原来的链表在整个链表反转后是原来的 head 成为整个链表的最后一个节点。但现在 head 递归反转后的节点不一定是最后一个节点，所以记录后驱 successor（第 n + 1 一个节点)，反转后会 head 连接上。

ps 图灵课堂老师从近一百套最新一线互联网公司面试题中精选而出，涵盖Java架构面试 所有技术栈，包括JVM，Mysql，并发，Spring，Redis，MQ，Zookeeper，Netty， Dubbo，Spring Boot，Spring Cloud，数据结构与算法，设计模式等相关技术领域的大 厂面试题及详解。 详情咨询客服获取全套面经试题。