题目：输入一个链表，反转链表后，输出链表的所有元素。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
方法一 递归
public class Solution {
ListNode node = null;
public ListNode ReverseList(ListNode head) {
if(head == null ||head.next == null){
return head;
}
node = ReverseList(head.next);
head.next.next = head;
head.next = null;
return node;
}
}
一般情况下反转的问题利用递归代码写起来是比较简洁的，但是也用调用栈过深导致溢出的缺点，并且对递归函数调用前后的的代码块的特点也有要一定的理解。
- 函数调用之后的代码块一般都是按照递归栈，从栈底向栈顶反向执行的。
- 函数调用之前的代码快是从栈顶到栈底执行的。
- 所以判断递归的结束条件要在递归函数的调用之前进行，
- 而需要进行反向的代码在递归函数调用之后进行。
本题中，最终要返回反转之后的头结点，所以
- 可以确定return的值为最后一个节点，不断的向上浮动
- 然后就是节点之间的关系反转
开始时第k个节点的next指向k+1，要将他反转过来变成k+1的next指向k。这个反转过程要从后向前进行。如果从前向后进行，就会导致1->2, 变成 2->1 和3节点就断开了。如果是反向的话4->5->6 反转之后是4->5<-6，链表仍然是相连接的。
方法二
public class Solution {
ListNode node;
public ListNode ReverseList(ListNode head) {
ListNode first = null;
ListNode second = null;
while(head != null){
first = head.next;
head.next = second;
second = head;
head = first;
}
return second;
}
}
上面使用递归的解释中提到，正向反转的话会出现链表断裂的情况，找不到下一个节点，那么我们可以使用一个指针一直指向下一个节点，然后将这个指针的next指向上一个节点即可。
