一、问题描述
初始状态：
目标状态：
二、递归法
反转单向链表
思路：先从前面递归到后面，使得每次递归时的指针指向当前结点的前一个结点；执行时从最后面的两个结点开始反转，依次向前，将后一个链表结点指向前一个结点，注意每次反转后要将原链表中前一个结点的指针域置空，表示将原链表中前一个结点指向后一个结点的指向关系断开。
ListNode * ReverseList(ListNode * head)
{
//递归终止条件：找到链表最后一个结点
if (head == NULL || head->next == NULL)
return head;
else
{
ListNode * newhead = ReverseList(head->next);//先反转后面的链表，从最后面的两个结点开始反转，依次向前
head->next->next = head;//将后一个链表结点指向前一个结点
head->next = NULL;//将原链表中前一个结点指向后一个结点的指向关系断开
return newhead;
}
}
理解：假如要当前要反转1->2，head永远指向结点1，而newhead是个固定值指向结点5.
三、非递归法
单链表反转的递归方法和非递归方法
代码一：
思路：利用两个结点指针和一个头结点指针head(用来记录当前结点的位置)，分别指向前一个结点、当前结点和下一个结点，每次循环让当前结点的指针域指向前一个结点即可；每一次翻转前需要先保存当前节点的下一个结点，再进行翻转，然后更新另外两个结点指针。
public ListNode reverseList(ListNode head) {
ListNode next = null;
ListNode pre = null
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
理解：假如1->2，则next指向2，且每次更新为2指向的结点；pre指向1，且每次更新为1指向的结点。
代码二
ListNode* reverseList2(ListNode* head) {
if (head == NULL || head->next == NULL)
return head;
ListNode* prev = head;
ListNode* cur = head->next;
ListNode* temp = head->next->next;
while (cur){
temp = cur->next; //temp作为中间节点，记录当前结点的下一个节点的位置
cur->next = prev; //当前结点指向前一个节点
prev = cur; //指针后移
cur = temp; //指针后移，处理下一个节点
}
head->next = NULL; //while结束后，将翻转后的最后一个节点（即翻转前的第一个结点head）的链域置为NULL
return prev;
}
代码二与代码一思路一样！
