题解 | #反转链表#

import java.util.*;

/*
 * 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) {
		// 如果是空链表直接返回
        if (head == null) {
            return null;
        }
		// 用堆来做，堆的特性是先进后出，所以头进去尾出来，堆最上面的元素就是链表的最后一个元素
        Stack<ListNode> stack = new Stack<>();
		// 循环条件为当前节点非空
        while (head != null) {
			// 将当前节点压入堆
            stack.push(head);
		    // 移到到下个节点
            head = head.next;
        }
	    // 此时堆顶部为反转链表的头结点
        ListNode node = stack.pop();
	    // 因为node指针要移动，所以创建变量newHead来记录反转后链表的头结点
        ListNode newHead = node;
	    // 循环条件为堆非空
        while (!stack.isEmpty()) {
		    // 从堆中取出
            ListNode tempNode = stack.pop();
		    // 一开始node是指向头结点的，所以这里要记录下个节点是谁
            node.next = tempNode;
		    // 移动到下个节点
            node = node.next;
        }
	    // 最后一个指向空
        node.next = null;
        return newHead;
    }
}