链表题目总结 -- 递归

一. 递归反转整个链表

• 题目链接：https://leetcode.cn/problems/reverse-linked-list/

1. 思路简述

• 所谓递归，就像那句歌词一样“一层一层剥开我的心”，我们从第一个节点一直向下探索，发现节点5。现在想：如果是单个节点，那反转链表其实就相当于自身本身，也就是不用动了。这里考虑一个临界情况，如果传进的参数（head指针）是null，那也不用动了，直接返回其本身就可以。
• 来到倒数第二层，也就是节点4，现在情况变成了节点有2个的链表，现在需要反转，那么我们只需要将中间的指针做一个反转就好了，而当前传进来的指针（head），其实是节点4的head指针，那么就有head.next.next = head；，最后将节点4的后继赋值为空（head.next = null），这表示这一阶段（有2个节点的链表已经反转完成。如果链表只有两个节点，直接输出就可以。）
• 重复上面步骤，直到最后整个链表都反转了
  

2. 代码

/*** Definition for singly-linked list.* public 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 {                       public ListNode reverseList(ListNode head) {//从后向前，一点点的进行反转//先分析特殊情况，链表有一个节点或者没有节点，直接返回头结点if(head == null || head.next == null)return head;else{//last为反转链表之后的头指针ListNode last = reverseList(head.next);head.next.next = head;head.next = null;return last;}}
}

3. 总结

• 时间复杂度：o(n)
• 空间复杂度：o(n)，需要用栈
• 第一次做的时候，还以为是逆向输出，整了半天，搞错了。
• 对递归的边界条件掌握的还是不好，像head == null这一块，博主当时就没想到与head.next进行合并。
• head.next = null;一定要注意，否则，会出现成环的现象

二. 反转链表前 N 个节点

• 题目链接：没有链接，给一个函数名：public static ListNode reverseN(ListNode head,int n)；，自己去练吧。

1. 思路简述

• 本质和反转链表差不多，只是在边界值的地方需要注意，

2. 代码

		//存放需要逆转链表的后继第一个节点public static ListNode successor = null;public static ListNode reverseN(ListNode head,int n){//逆转前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;}

3. 总结

• 也就是反转链表，只是每次反转完，head后面要接后继节点（后面的一段不需要反转的链表），就变了这一点。
• 时间复杂度：o(n)
• 空间复杂度：o(n)，需要用栈

三、反转链表的一部分

• 题目链接：https://leetcode.cn/problems/reverse-linked-list-ii/

1. 思路简述

• 将问题转换成反转前n个节点的问题。

2. 代码

	//存放需要逆转链表的后继第一个节点public static ListNode successor = null;public static ListNode reverseN(ListNode head,int n){//逆转前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;}ListNode reverseBetween(ListNode head, int m, int n) {// 当m为1的时候，装换成了反转前面几个节点的链表的问题if (m == 1) {return reverseN(head, n);}// 将前面不需要反转的链表和后面反转过的链表接在一起head.next = reverseBetween(head.next, m - 1, n - 1);return head;}

3.总结

• head.next = reverseBetween(head.next, m - 1, n - 1); 为什么是head.next呢，看边界情况，m = 1时，返回的是后面已经反转过的链表，也就是说前面的链表压根不需要反转，只要把它们拼接在一起就行了。
• 再说为什么是m - 1的问题，每递归一次，新链表就会从前面缩短一节，那么对于新链表来说，就是从第m-1个节点开始反转，到第n - 1个节点结束反转。这里的关键是链表从头开始缩短了，所以，m - 1 和 n - 1都要存在。

四、从节点M开始反转后面的链表

• 题目链接：没有链接，给一个函数名：public static ListNode reverseP(ListNode head,int m)；，自己去练吧。

1. 思路简述

• 转换成反转单链表的问题

2. 代码

    public ListNode reverseList(ListNode head) {//从后向前，一点点的进行反转//先分析特殊情况，链表有一个节点或者没有节点，直接返回头结点if(head == null || head.next == null)return head;else{//last为反转链表之后的头指针ListNode last = reverseList(head.next);head.next.next = head;head.next = null;return last;}}public static ListNode reverseP(ListNode head, int m){//转换成反转链表的问题if(m == 1){return reverseList(head);}head.next = reverseP(head.next, m - 1);return head;}

3.总结

• 和上一题差不多，一直递归，到链表需要反转的地方（m == 1），开始反转整个单链表。

参考：https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-8f30d/di-gui-mo–10b77/