Leetcode206. 反转链表

题目描述

给你单链表的头节点 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);
    }
}

其实双指针法之前是知道的，但是太长时间没碰算法了，看到了就想起来了，后悔这段时间为什么不温习一下之前的知识