定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

限制：

链表的反转是老生常谈的一个问题了，同时也是面试中常考的一道题。最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。原理如下

代码比较简单，来看下

 1public ListNode reverseList(ListNode head) {
 2    Stack<ListNode> stack = new Stack<>();
 3    //把链表节点全部摘掉放到栈中
 4    while (head != null) {
 5        stack.push(head);
 6        head = head.next;
 7    }
 8    if (stack.isEmpty())
 9        return null;
10    ListNode node = stack.pop();
11    ListNode dummy = node;
12    //栈中的结点全部出栈，然后重新连成一个新的链表
13    while (!stack.isEmpty()) {
14        ListNode tempNode = stack.pop();
15        node.next = tempNode;
16        node = node.next;
17    }
18    //最后一个结点就是反转前的头结点，一定要让他的next
19    //等于空，否则会构成环
20    node.next = null;
21    return dummy;
22}

双链表求解是把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表。下面以链表1→2→3→4为例画个图来看下。

 1public ListNode reverseList(ListNode head) {
 2    //新链表
 3    ListNode newHead = null;
 4    while (head != null) {
 5        //先保存访问的节点的下一个节点，保存起来
 6        //留着下一步访问的
 7        ListNode temp = head.next;
 8        //每次访问的原链表节点都会成为新链表的头结点，
 9        //其实就是把新链表挂到访问的原链表节点的
10        //后面就行了
11        head.next = newHead;
12        //更新新链表
13        newHead = head;
14        //重新赋值，继续访问
15        head = temp;
16    }
17    //返回新链表
18    return newHead;
19}

我们再来回顾一下递归的模板，终止条件，递归调用，逻辑处理。

 1public ListNode reverseList(参数0) {
 2    if (终止条件)
 3        return;
 4
 5    逻辑处理（可能有，也可能没有，具体问题具体分析）
 6
 7    //递归调用
 8    ListNode reverse = reverseList(参数1);
 9
10    逻辑处理（可能有，也可能没有，具体问题具体分析）
11}

 1public ListNode reverseList(ListNode head) {
 2    //终止条件
 3    if (head == null || head.next == null)
 4        return head;
 5    //保存当前节点的下一个结点
 6    ListNode next = head.next;
 7    //从当前节点的下一个结点开始递归调用
 8    ListNode reverse = reverseList(next);
 9    //reverse是反转之后的链表，因为函数reverseList
10    // 表示的是对链表的反转，所以反转完之后next肯定
11    // 是链表reverse的尾结点，然后我们再把当前节点
12    //head挂到next节点的后面就完成了链表的反转。
13    next.next = head;
14    //这里head相当于变成了尾结点，尾结点都是为空的，
15    //否则会构成环
16    head.next = null;
17    return reverse;
18}

1public ListNode reverseList(ListNode head) {
2    if (head == null || head.next == null)
3        return head;
4    ListNode reverse = reverseList(head.next);
5    head.next.next = head;
6    head.next = null;
7    return reverse;
8}

 1public ListNode reverseList(ListNode head) {
 2    return reverseListInt(head, null);
 3}
 4
 5private ListNode reverseListInt(ListNode head, ListNode newHead) {
 6    if (head == null)
 7        return newHead;
 8    ListNode next = head.next;
 9    head.next = newHead;
10    return reverseListInt(next, head);
11}

 1public ListNode reverseList(ListNode head) {
 2    return reverseListInt(head, null);
 3}
 4
 5private ListNode reverseListInt(ListNode head, ListNode newHead) {
 6    if (head == null)
 7        return newHead;
 8    ListNode next = head.next;
 9    head.next = newHead;
10    ListNode node = reverseListInt(next, head);
11    return node;
12}

链表反转使用栈虽然也能实现，但一般不是很推荐，下面两种实现方式会好一些。使用栈能实现链表的反转，那么使用队列呢，如果使用双端队列也是可以的，从一端全部入队，然后再从这一端全部出队，说了半天这不还是和栈一样吗……