206 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

1.创建新的头结点

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newNode=new ListNode();
        ListNode next=null;
        ListNode cur=head;
        while(cur!=null){
           next=cur.next;
           cur.next=newNode.next;
           newNode.next=cur;
           cur=next;
        }
        return newNode.next;
    }
}

思路：
定义另外一个（头）结点
从头遍历节点，每遍历一个节点将其取出，放到temp的最前端。

2.双指针(迭代)

其实和创建头节很相似

 public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode current=head;
        ListNode temp=null;
        while(current!=null){
            //保存当前节点current的下一个节点
            temp=current.next;
            //current改变方向，反转
            current.next=pre;
            //pre  cur往后一位
            pre=current;
            current=temp;
        }
        return pre;
    }

3.递归

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归的退出条件，head.next==null,表明只有一个元素，不需要反转
       if(head==null ||head.next==null){
           return head;
       }
       //需要用变量保存返回值
       ListNode cur= reverseList(head.next);
       //1-2-3-4-5， 让5?4，反转
       head.next.next=head;
       //防止形成环，取消4?5，head.next置空
       head.next=null;
       //每层递归函数返回的是没有被反转的最后一个节点
       return cur;
    }
}

当前链表的次节点往后都已经反转好了，所以只要反转头两个节点就可以了。这也是curr固定的原因，
cur就是原链表的最后一个节点。所以返回它。（这里画图理解更好）

【链表】反转链表的三个做法（力扣206）

原文：https://www.cnblogs.com/My-Coding-Life/p/14758061.html