反转链表

算法思想

1. 初始条件，头结点不能为null，否则直接返回null
2. 对于第i个节点，我们只要得到第i+1到last节点的逆序链表。假设第i+1到last节点的逆序链表的最后一个元素叫prev，那我们只要把prev.next设置为当前节点，并返回当前节点即可
3. 对于最后一个节点last，last.next是null，我们直接返回last即可
4. 以上三步可以逆序，但我们好像没保存新的头结点（原来的尾节点），第三部保存一下即可

上代码

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    protected ListNode newHead;
    public ListNode ReverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode last = ReverseListRecursive(head);
        last.next = null;
        return newHead;
    }

    public ListNode ReverseListRecursive(ListNode node) {
        if(node.next != null){
            ListNode prev = ReverseListRecursive(node.next);
            prev.next = node;
            return node;
        }else{
            newHead = node;
            return node;
        }
    }
}