链表倒置.md

递归-链表倒置

递归

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。

每个递归定义必须至少有一个条件，当满足这个条件时递归不再进行，即函数不再调用自己而是返回。

简单的递归案例1：斐波那契数列：

斐波那契数列是如下的一组数字：

1 1 2 3 5 8 13 21 34 55 89 144 233 ...

其规律是：前两个数字都是1，从第三个数字开始，每个数字都是它前面两个数字的和。

要计算某个位置上的数字，可以使用递归的方法：

private static long getFibonacciAt(int num) {
    if (num < 2) {
        return 1;
    }
    return getFibonacciAt(num - 1) + getFibonacciAt(num - 2);
}

简单的递归案例2：整数的阶乘：

一个整数的阶乘是小于这个整数的所有正整数的乘积。一个数的阶乘用n!表示，如：

0! = 1
1! = 1
2! = 1 * 2
3! = 1 * 2 * 3
4! = 1 * 2 * 3 * 4
5! = 1 * 2 * 3 * 4 * 5

可见，一个数n的阶乘等于n与(n-1)的阶乘的乘积，且0!=1。求n!的代码如下：

private static long getFactorial(int num) {
    if (0 == num) {
        return 1;
    }
    return num * getFactorial(num - 1);
}

链表倒置

给定一个链表，要求输出它倒置后的数据。

代码如下：

private static void reverseList(ListNode node) {
    ListNode nextNode = node.next;
    if (null != nextNode) {
        reverseList(nextNode);
    }
    System.out.print(node.data + " ");
}