题解 | #反转链表#

列表反转：

1. 把所有节点统一缓存到容器里 ArrayList、Stack，
2. 缓存后顺便把当前节点的 next 制空，List 有天然的 index 不怕你找不到节点值
3. 倒叙读取 List 里的元素，从最后一个元素开始，每个元素指向前一个元素。最后一个节点不会是任何一个节点的 next，可以先取出，方便反转
4. node指向当前节点，向前移动，所以要把 node.next 赋值给 node
5. 反向之后，最后一个节点变成头节点

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) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        // 花点钱，申请块内存把节点全部缓存起来，再一一反转
        // List、Stack 都行
        List<ListNode> list = new ArrayList<>();
        while(head != null){
            list.add(head);
            head = head.next;
        }
        // 去除 next 的指向，避免反转混乱
        for(int i = 0; i<list.size()-1;i++){
            list.get(i).next = null;
        }
        // 辅助节点
        ListNode node = new ListNode(0);
        for(int i= list.size()-1;i>=0;i--){
            node.next = list.get(i);
            node = node.next; // node指向当前节点，向前移动
        }

        // head = list.get(list.size()-1);
        // for(int i= list.size()-2;i>=0;i--){
        //     head.next = list.get(i);
        //     head = head.next;
        // } 

        // for(int i = list.size()-1; i > 0; i--){
        //     ListNode tail = list.get(i);
        //     ListNode previous = list.get(i - 1);
        //     tail.next = previous;
        //     previous.next = null;
        // }
        // 反向之后，最后一个节点变成头节点
        head = list.get(list.size() - 1);
        
        return head;
    }
}