第一次在牛客上写题解，先那反转链表熟练一下吧。

1. 思路

那么，链表反转 应该怎么做呢？
最直接的想法应该是：
1）先遍历链表的元素，保存在stack中；
2）元素出栈，同时构建反转链表。
如此，则可以达到反转的目的。

但是，这样做，优雅吗？
显然不。要是可以在遍历的同时，就把反转链表给做了，岂不妙哉？！

一种可行的做法：
新建一个链表，这个链表有个头结点。
然后，遍历原链表，每当遍历一个原链表的值，就插入到这个伪头节点的后面。
如此，可以保证后面遍历的元素在新链表的前面。
即下述代码也。

2. 代码

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode cur = head;
        ListNode newHead = new ListNode(0);
        while (cur != null){
            ListNode tmp = new ListNode(cur.val);
            tmp.next = newHead.next;
            newHead.next = tmp;
            cur = cur.next;
        }
        return newHead.next;
    }
}

3. 结果

解法补充：

空间复杂度为 O(1)的解法：

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

题目中提到的栈解法：

import java.util.Stack;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while (cur!=null){
            stack.push(cur.val);
            cur = cur.next;
        }
        ListNode newHead = new ListNode(0);
        cur = newHead;
        while (!stack.isEmpty()){
            ListNode tmp = new ListNode(stack.pop());
            cur.next = tmp;
            cur = cur.next;
        }
        return newHead.next;
    }
}