题解 | #反转链表#

import java.util.*;
import java.util.Stack;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        Stack<ListNode> stack = new Stack<>(); //生成栈stack
        ListNode copyhead = head;              //思考一下head.next的值，可能你就错在这里了。
        //把链表节点全部摘掉放到栈中
        while (copyhead != null){
            stack.push(copyhead);                   //push()放入栈
            copyhead = copyhead.next;                   //head指向下一个结点
        }
        
        if(stack.isEmpty()){                    //isEmpty()判断栈是否为空
            return null;
        }
        ListNode node = stack.pop();            //第一次pop()出栈，即头结点
        ListNode newhead = node;                //新的头节点诞生
        //栈中的结点全部出栈
        while (!stack.isEmpty()){
            node.next = stack.pop();             //从头结点的下一个结点开始，循环出栈
            node = node.next;                    //node指向下一个结点
        }
        /*最后一个结点就是反转前的头结点，
        由于刚开始的头结点head存放的下一个结点地址不为空，
        且指向的一定是head.next或null(只有一个头结点);
        这就是为什么我会多一步ListNode copyhead = head; 
        一定要让它的next等于空，否则会构成环*/
        node.next = null;
        return newhead;
    }
}