题目：反转单链表 1 -2 - 3 - 4 输出 4

    • 3 -2 - 1


    解题：

    //用递归的方法实现反转
    public static int reverseList（Node list1）{
    //临界条件判断
    if( list1== null || list1.next == null) return list1;

    //递归反转子链表
    Node newList = reverseList（list1.next）;
    // 通过list1.next 获取节点2

    Node t = list1.next;
    //让2的next指向2

    t.next = list1 ;
    //1的next指向null
    list1.next = null;
    //把调整好的链表返回
    return newList;

    }

    递归优化知识点：

    虽然递归可以解这题， 但是会存储重复计算， 如果节点数越大， 重复结算率就越高，这样是不可取的
    所以我么可以采用java的hashmap来解决该题， 只要将计算过的结果保存起来， 下次遇到相同的计算直接调用上次的结算结果即可。
    如下参考代码：

    //假定数组arr[n] 已经初始化了int f(int n) {
    if (n < -1) {
    return n; }
    }

    //首先判断当前是否计算过
    //用 -1 来标记计算过的状态
    if(arr[n] != -1){
    //计算过，直接返回
    return arr[n];
    }else{
    //没有计算过，则递归计算，并结果保存到arr数组中
    arr[n] = f(n - 1) + f(n - 2);
    return arr[n];
    }