反转一个单链表：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
一、 迭代法
注意观察示例：1->2->3->4->5->NULL 的反转可以看成：NULL<-1<-2<-3<-4<-5。
会发现链表的反转基本上就是箭头的方向的反转，即节点前驱和后继互换角色。定义三个变量 cur，pre 和 next 分别表示当前节点，以及其前驱后继。cur 初始化为 head，其他初始化为 NULL。
从头节点 1 开始遍历，1 的 next 和 pre 原来分别是2和 NULL(初始值)互换后1的 next 和 pre 变成 NULL 和 2，依次这样遍历下去。
注意最后应该返回 pre，不是 cur。遍历结束后 cur 的值是 NULL。
代码如下：
public ListNode reverseList(ListNode head){
ListNode pre = null, cur = head, next = null;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
二、递归法
递归法和迭代法思路是一样的。
代码如下：
public ListNode reverseList(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode n = reverseList(head.next);
head.next.next = head;
head.next = null;
return n;
}
只是注意两个地方：
如果 head 是空或者遍历到最后节点的时候，应该返回 head。
代码 5，6 行。节点替换的时候不要用 n 来代替 head->next。因为对于递归来说它们不是等价的。但是 head->next->next 等价于 n->next。
