列表反转–递归法
要明白两个问题：
列表反转是什么？
递归是什么?
列表反转是什么？
有一个列表:1->2->3->4->5
列表反转就是5->4->3->2->1
递归是什么?
递归就是自己调用自己的过程，且递归一定要有一个推出递归的条件，不然就会成为死循环。
递归的思想就是把大问题化解成一个个小问题，通过解决这些小问题，最终大问题就会被解决。
递归图示:
当参数传递到递归函数中，然后调用自己，直到递归的条件不成立，退出最后一层递归，然后返回到上层递归中，执行调用自己这条语句下面的代码如此往复，直至回到第一次被调用的地方。
解决链表反转的递归思路是：
我们假设只有五个结点，把反转整个链表看成一个大问题，那么小问题就是有A结点与B结点的反转,B结点与C结点的反转,C结点与D结点的反转，D结点与E结点的反转。这样的话，就有四个小问题要解决。
我们可以这样
核心
head.next.next=head
head.next=Null
head.next表示第二个结点
head.next.next表示第二个结点指向第三个结点
我们把head.next.next=head表示把第二个结点指向第一个结点，然后head.next=null表示第一个结点的指针置为空
但是此时问题来了，这样做，我们确实把第一个小问题给解决了，但是，我们这时发现，第三个结点找不到了。因为第二个结点到第三个结点的指针断了。
所以我们可以换种思路，从最后一个小问题开始，也就是D.next.next=D
D.next=null
此时，D前面的链表还没有断掉，指针依然可以指向原来的结点。
代码：
package Linked_List;
/**
* @author:MrQ
* @date 2021/7/22-17:52
*/
public class TraverseList {
static class LNode{
int Data;//存放数据
LNode Next;//指向下一结点
public LNode(int data, LNode next) {
this.Data = data;
this.Next = next;
}
}
/**
* 使用递归的方法翻转链表
* @param Head
* @return
*/
public static LNode recursion(LNode Head){
//递归调用前需要判断是否为空表或者是否到达了最后一个结点,如果不是，则递归调用函数往下面遍历
if (Head == null || Head.Next == null){ //当链表为空或到了链表的尾结点，直接返回当前结点
return Head;
}
LNode new_head = recursion(Head.Next);//递归调用函数，最后Head将会到尾结点
Head.Next.Next=Head; //在本例中，执行到第五个结点会跳出递归，那么此时Head执行第四个结点
Head.Next=null;
return new_head;
}
public static void main(String[] args) {
LNode node5 = new LNode(5,null);
LNode node4 = new LNode(4,node5);
LNode node3 = new LNode(3,node4);
LNode node2 = new LNode(2,node3);
LNode node1 = new LNode(1,node2);
LNode recursion_node = recursion(node1);
System.out.println(recursion_node);
}
}
结合代码，递归就是这样使用的
当头节点传递进去之后，调用递归函数，结点会一直往后遍历，直到head.Data=5时，也就是第五个结点，head.next为空，此时利用递归函数传递的参数head为第四个结点，返回head
之后head.next.next=head，就是第五个结点的指针指向第四个结点，第四个结点的指针指向空，如此反复，直到第一个结点
在每一个递归中返回的new_head都是第五个结点，到最后，第五个结点将会出现在第一个结点的位置。
此时，链表已经反转完成