翻转链表
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路分析
双指针法是本体的最基本的解法，由此还可以改写为递归解法
双指针法
我们需要定义两个指针，pre和cur
初始时，cur指向头节点，pre指向null（pre需要在cur之前，前面又没有节点，那只能是null咯。或者可以这么理解：翻转之后此时pre的位置会变成链表尾部，那链表尾部肯定指向null，所以需要将pre初始化为null）
让cur指向前一个节点
此时为了保存cur的下一个节点，好翻转之后让指针顺利移动到下一位置，我们需要先有一个临时节点temp
然后先把pre移动到当前cur的位置
再根据temp将cur移动到正确的下移位置
注意：这里先移动cur再移动pre的话会导致pre移动到的并不是之前cur的位置，因为cur的值已经先于pre改变（刻舟求剑懂不懂？）
之后就重复上述步骤即可
那么什么时候结束循环呢？当cur指到原链表的尾部（null）时便可结束，此时pre指向的节点为新的头节点
代码
明确步骤之后代码就很好写了
class Solution {
public ListNode reverseList(ListNode head) {
//双指针法
//初始化两个指针
ListNode cur = head;
ListNode pre = null;
//定义用于存放cur下一节点的临时节点temp
ListNode temp;
while(cur != null){//从旧的头节点开始遍历，到翻转前的链表尾部（也就是null）结束
temp = cur.next;
cur.next = pre;
//注意，cur翻转完之后一定先让pre按照当前cur的值移动到指定位置，再让cur更新为temp
//不然cur先动了pre就找不到之前cur的位置了
pre = cur;
cur = temp;
}
return pre;//翻转结束，此时pre指向的就是新的头节点
}
}
递归法
递归法主要是针对双指针法在代码层面上的一个优化，原理层面与双指针法一致
因此递归法的代码可以与双指针法的一一对应
代码
LeetCode上解题模板中，Solution类给了一个主方法reverseList
那么根据递归的写法，我们还要写一个reverse方法，让reverseList去调用它来翻转链表
class Solution {
public ListNode reverse(ListNode pre, ListNode cur){
}
public ListNode reverseList(ListNode head) {
reverse();
}
}
reverseList传入的参数是head，那么reverse需要的两个参数怎么传？
参考双指针法的初始化部分，reverse中的两个参数也要对应进行初始化
即：
class Solution {
public ListNode reverse(ListNode pre, ListNode cur){
}
public ListNode reverseList(ListNode head) {
reverse(null， head);//与双指针法对应
}
}
接下来按照双指针思路把reverse的功能完善即可，完整代码如下：
class Solution {
public ListNode reverse(ListNode cur, ListNode pre){
ListNode temp;
if(cur == null){
return pre;
}
temp = cur.next;//保存cur.next
cur.next = pre;//翻转操作
//接下来要让pre和cur整体向后移动一位，在递归里应该直接用return来实现，下面代码对应于
//pre = cur;
//cur = temp;
return reverse(temp, cur);//进入下一层递归
}
public ListNode reverseList(ListNode head) {
return reverse(head, null);//与双指针法对应
}
}
