递归
递归递归，有递要有归！
需求有一个链表，原本顺序如下： 1 》 2 》3 》4
需要使用递归将其反转： 4 》 3 》2 》1
核心代码测试代码
public static void main(String[] args) {LinkList<Integer> list = new LinkList<>();list.insert(1);list.insert(2);list.insert(3);list.insert(4);Iterator<Integer> it = list.iterator();System.out.println("反转前：");while (it.hasNext()) {System.out.print(it.next() + " ");}list.reverse();反转代码
public void reverse() {if (isEmpty()) {return;}reverse(head.next);}private Node reverse(Node curr) {if (curr.next == null) {head.next = curr;return curr;}Node pre = reverse(curr.next);pre.next = curr;curr.next = null;return curr;} 递归调用过程方法调用内存图如下：
首先执行的是main方法main方法进栈，然后调用main方法中的reverse()方法，reverse()方法进栈。reverse() 方法调用带参数 重载的reverse(1) 方法。reverse(1) 方法进栈，当方法执行到Node pre = reverse(2)时。reverse(2) 方法进栈，当方法执行到Node pre = reverse(3)时。reverse(3) 方法进栈，当方法执行到Node pre = reverse(4)时。reverse(4) 方法进栈， 当执行reverse(4) 方法时， 会首先进行判断curr.next == null ，然后满足条件，让头结点指向 4 这个结点 ，该方法返回一个结点 （4结点 临界值）。（这个返回值是返回给 reverse(3) 的，然后reverse(4) 执行完毕，出栈）当前链表的头结点指向图： reverse(4) 出栈
此时 reverse(3) 接收 reverse(4) 的返回值 此时 当前pre 是4结点 ，执行 剩余的代码pre.next = curr; 将 4 结点 的下一个结点指向 3 结点curr.next = null; 将 3 结点 的下一个结点指向 null （原本 3 结点指向的 是 4 结点，现在将其断开了）reverse(3) 执行完毕后，将返回值（返回的是3结点）给 reverse(2) ， 然后出栈。当前链表的头结点指向图：
reverse(3) 出栈
此时 reverse(2) 接收 reverse(3) 的返回值 此时 当前pre 是3结点 ，执行 剩余的代码pre.next = curr; 将 3 结点 的下一个结点指向 2 结点curr.next = null; 将 2 结点 的下一个结点指向 null （原本 2 结点指向的 是 3 结点，现在将其断开了）reverse(2) 执行完毕后，将返回值（返回的是2结点）给 reverse(1) ， 然后出栈。当前链表的头结点指向图： reverse(2) 出栈
此时 reverse(1) 接收 reverse(2) 的返回值 此时 当前pre 是2结点 ，执行 剩余的代码pre.next = curr; 将 2 结点 的下一个结点指向 1 结点curr.next = null; 将 1 结点 的下一个结点指向 null （原本 1 结点指向的 是 2 结点，现在将其断开了）reverse(1) 执行完毕后，将返回值（返回的是1结点）给 reverse() 方法（该方法没有使用变量接收返回值 ）， 然后出栈。当前链表的头结点指向图：
reverse(1) 出栈
到此，使用递归反转单链表的功能已经实现了
灵感来源blog.csdn.net/ITdevil/article/details/76152869
递归