题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例
提交的代码
class Solution {
public ListNode resultHead;
public ListNode reverseList(ListNode head) {
if(head==null)return null;
ListNode first=recursionOfList(head);
first.next=null;
return resultHead;
}
public ListNode recursionOfList(ListNode node){
ListNode returnedNode=null;
if(node.next!=null){
returnedNode=recursionOfList(node.next);
}
if(node.next==null){
resultHead=node;
return node;
}
returnedNode.next=node;
return node;
}
}
使用递归的方法来实现反转。
递归到最后一个节点以后，返回当前节点给倒数第二个节点，并让返回的节点next指向倒数第二个节点，一直往上递归，这里需要记住将最后一个节点的地址记录，并且递归结束以后要将最后一个节点的next置为null，不然会出现循环的情况。
学习到的方法
双指针法遍历(虽然有三个指针，但是重点是前两个)，直接让cur的next指向pre，需要注意的是需要再设置一个next指针指向cur的下一个节点，因为cur的next是会改变的，遍历题目给出的链表需要记录它。
代码为：
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null)return null;
ListNode pre=null;
ListNode cur=head;
ListNode nextNode;
while(cur!=null){
nextNode=cur.next;
cur.next=pre;
pre=cur;
cur=nextNode;
}
return pre;
}
}
另一种队规方法和上面的双指针法一致，虽然我觉得我的方法适合我，但是个人还是用递归实现一下上面的方法，用来加深个人对于递归的理解。
以下为递归实现的双指针法代码：
class Solution {
ListNode nextNode;
public ListNode reverseList(ListNode head) {
return recursionMethod(null,head);
}
public ListNode recursionMethod(ListNode pre,ListNode cur){
if(cur==null)return pre;
//记录下来当前节点的下一节点，因为当前节点的next待会会改变。
nextNode=cur.next;
//当前节点的翻转开始
cur.next=pre;
pre=cur;
cur=nextNode;
return recursionMethod(pre,cur);
}
}
其实双指针法之前是知道的，但是太长时间没碰算法了，看到了就想起来了，后悔这段时间为什么不温习一下之前的知识