方案1 栈模拟

使用栈模拟，然后构建正确的关系（即next之间的关系）即可。

栈：先进后出，后进先出

/*
栈扫描即可
*/
public class Solution {
  	//用数组模拟栈的操作
    public ListNode[] q = new ListNode[1010];
    public ListNode ReverseList(ListNode head) {
      	//特判
        if(head == null)return head;
      	//栈的位置[当前处于哪里]
        int tt = -1;
        while(head != null){
            q[++tt] = head;
            ListNode tmp = head.next;
          	//将next置空
            head.next = null;
            head = tmp;
        }
      	//构建新的结果集
        ListNode ret = q[tt];
        while(tt > 0){
            q[tt].next = q[tt - 1];
            tt--;
        }
        return ret;
    }
}

时空复杂度：O(n) O(n)

方案2 双指针

在做题的时候，我发现，只用每次重构相邻之间的next的关系就可以了，于是便想出了可以使用双指针去解决这个题，这个思路不好描述，所以我针对样例的 1-->2-->3进行模拟，如下图：

/*
双指针
*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null)return head;
        //存储t2.next 因为要将t2.next设为t1，所以需要记录
        ListNode tmp = null;
        //相邻的两个节点
        ListNode t1 = head;
        ListNode t2 = head.next;
        do{
            tmp = t2.next;
            t2.next = t1;
            t1 = t2;
            t2 = tmp;
        }while(t2 != null);
        //头节点需要设置一下，不然在第一个节点和第二个节点会产生环
        head.next = null;
        return t1;
    }
}

时空复杂度 O(n) O(1)