反转链表（老反转了）

1. 反转链表

①递归

// 1 -> 2 -> 3 -> 4 -> 5 -> null
// null -> 5 -> 4 -> 3 -> 2 -> 1
//两种方法，然后我们分别说一下这两种方法 第一种是递归  第二种是迭代
/**
递归 开始是这样子的
    1 -> 2 -> 3 -> 4 -> 5 -> null
    递归的思想是直接反转
    1 -> 2 -> 3 -> 4 <- 5 
    从后往前指 本来 5这个节点的next指的是null 现在让next 指向 前一个节点 也就等于目前 4这个节点的next的节点的next节点指向自己
    head.next.next = head; 实现反转
**/
//节点类
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        this.val = x;
    }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;   //主要是实现对反转后最后的一个节点的next 设为null
        return p;           //这里 P 会为之前最后一个不为null的值 将其作为反转后的firsthead 返回
    }
}

/**
递归比较复杂，因为递归会使用隐式栈空间，递归深度可能会达到n层所以有空间复杂度
一般情况我们其实是不建议在程序中用递归的
空间复杂度：O(n)
时间复杂度：O(n)
**/

②迭代

// 1 -> 2 -> 3 -> 4 -> 5 -> null
// 5 -> 4 -> 3 -> 2 -> 1 -> null
/**
迭代是通过遍历，然后将其反转，具体操作是这样子的

首先 我们声明两个 ListNode 对象 一个为prev 用来保存 要反转链表的原来的上一个节点  一个为curr 用来保存 要反转链表的 当前节点，好让节点继续向下滚动 去反转
当我们在 当前 节点时，它的next 是 下一个节点 我们将对其保存， 然后对 当前 这个节点的next 改变，改变成 上一个 节点，这样就做到了 比如： 1 -> null     2 -> 1
然后需要对其 当前节点变为 之前保存的那个节点 好让节点往下继续 反转下去
ListNode nextTemp = curr.next;  //保存下一个节点
curr.next = prev;               //将next 指向进行改变
prev = curr;                    //反转节点
curr = nextTemp;                //对下一个节点进行传入准备进行反转
**/
//节点类
public class ListNode {
    int val;
    ListNode next;
    ListNode (int x) {
        this.val = x;
    }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while(curr != null) {
            ListNode nextTemp = curr.next;
        }
    }
}
/**
空间复杂度：O(1)
时间复杂度：O(n)
**/