输入一个链表的头结点，反转链表后，并返回反转链表的头结点。
为了避免断裂现象的发生，应该设置三个节点指针去检查。即为了在指针指向改变之前记录下下一个节点，改变后记录下下一次改变的上一个节点，即当前节点。当前节点下移到记录的下一个节点。
代码如下：
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
/***利用三个指针操作，通过将所有指向反向
* 最后一个节点作为头结点
*
* @param head
* @return
*/
public ListNode ReverseList(ListNode head) {
if (head == null){
return null;
}
ListNode cur = head;
ListNode pre = null;
ListNode next = null;
while (cur != null){
//在cur改变指向之前，先用next保存cur原来的指向,防止节点出现断链
next = cur.next;
//先让其指向空节点
cur.next = pre;
//把上个节点赋给空节点
pre = cur;
//这时候，cur的指向已经改变
cur = next;
}
return pre;
}
递归反转链表
递归栈记录下链表的顺序后，每个节点都当做头结点来处理
代码如下：
/**
* 递归每次改变头结点输入，作头结点和后节点的交换
* @param head
* @return
*/
public ListNode ReverseList2(ListNode head) {
if (head == null || head.next == null){
return head;
}
//递归结果为最后一个节点
ListNode newHead = ReverseList2(head.next);
//交换每个新头节点的指向
ListNode pNode = head.next;
pNode.next = head;
//去掉头结点指向
head.next = null;
return newHead;
}
}
