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) {
	   // 记录前驱节点、当前节点
        ListNode prev = null;
        ListNode curr = head;
	   // 循环条件当前节点不为null
        while (curr != null) {
		  // 记录后继结点
            ListNode next = curr.next;
		  // 记录完后继结点后，才把前驱节点的下一步赋值为prev,类似尾插法，先把第一个结点的next指向null,然后再把第二个结点的next指向第一个结点，以此类推
            curr.next = prev;
		  // 前驱结点向后走一步
            prev = curr;
		  // 当前节点向后走一步
            curr = next;
        }
	   // 返回前驱结点,因为跳出循环的条件是curr==null,那么prev就是最后一个有值的节点，返回即可
        return prev;
    }
  /**
  解法二: 栈或者哈希
  */
   public ListNode ReverseList(ListNode head) {
	 // 创建栈存结点
       Stack<ListNode> stack = new Stack<>();
	 // 遍历链表，并存到栈中
        while(head!=null){
            stack.push(head);
            head=head.next;
        }
	 // 如果栈为空，直接返回null
        if(stack.isEmpty()){
            return null;
        }
	 // 根据栈的先入后出的特性，开始出栈
        ListNode lastNode = stack.pop();
	 // 赋值给一个新的头结点,并最终要返回这个新的头结点
        ListNode newHead = lastNode;
	 // 循环条件：栈不为空 一边遍历一边出栈，将结点相连
        while(!stack.isEmpty()){
            ListNode temp = stack.pop();
            lastNode.next = temp;
            lastNode = lastNode.next;
        }
        //最后一个结点pop后，next赋值为null，防止形成环
        lastNode.next=null;
        return newHead;
    }
}

本题考察知识点:

1.链表的遍历

2.前驱结点和后继结点的相连

本题解题思路：

方法一：模拟

1.记录前驱节点、当前节点

2.循环条件当前节点不为null

3.记录后继结点

4.记录完后继结点后，才把前驱节点的下一步赋值为prev,类似尾插法，先把第一个结点的next指向null,然后再把第二个结点的next指向第一个结点，以此类推

5.前驱结点向后走一步

6.当前节点向后走一步

7.返回前驱结点,因为跳出循环的条件是curr==null,那么prev就是最后一个有值的节点，返回即可

方法二：栈

直接看注释就可以了非常完善捏

如果您觉得本题对您有帮助的话，可以点个赞支持一下，感谢~