A. 反转链表（⭐⭐⭐⭐⭐）

class Solution {
    public ListNode reverseList(ListNode head) {
        // 特殊判断
        if(head == null) return null;
        // 1. 初始化三个指针
        ListNode prev = head;
        ListNode cur = head.next;
        head.next = null;
        ListNode next;
        // 2. 进行反转，先记录next，cur指向prev
        while(cur != null) {
            next = cur.next;
            cur.next = prev;

            prev = cur;
            cur = next;
        }
				// 3. 最后返回prev，因为cur是null
        return prev;
    }
}

A. LRU缓存（⭐⭐⭐⭐⭐）

// 1. 定义一个节点
class Node {
    int key, val;
    Node prev, next;
    Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

// 2. 完成双向链表的addFirst和remove方法，其中用map实现O1查找节点
class DoubleLinkedList {
    Node head, tail;
    HashMap<Integer, Node> map = new HashMap<>();
    DoubleLinkedList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    public void addFrist(Node node) {
        node.next = head.next;
        node.prev = head;

        head.next.prev = node;
        head.next = node;
        map.put(node.key, node);
    }
    public void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        map.remove(node.key);
    }
    public void removeLast() {
        if(tail.prev != head) {
            remove(tail.prev);
        }
    }
    public Node search(int key) {
        return map.get(key);
    }
}
class LRUCache {
    DoubleLinkedList list = new DoubleLinkedList();
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    // 如果搜索一下节点，如果不存在返回-1，如果存在返回值，并移动到链表头
    public int get(int key) {
        Node node = list.search(key);
        if(node == null) return -1;
        list.remove(node);
        list.addFrist(node);
        return node.val;
    }
    
    // 如果存在，无论值一不一样都刷新
    // 如果不存在，但是满了，先删除。在添加
    public void put(int key, int value) {
        int val = get(key);
        Node node = new Node(key, value);
        // 
        if(val != -1) {
            Node oldNode = list.search(key);
            list.remove(oldNode);
            list.addFrist(node);
            return;
        }
        if(list.map.size() == this.capacity) {
            list.removeLast();
        }
        list.addFrist(node);
    }
}

A. 移除链表元素（⭐⭐⭐⭐）

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 1. 处理特殊情况
        if(head == null) return null;
        // 2. 创建虚拟节点
        ListNode virtual = new ListNode();
        ListNode prev = virtual;
        ListNode cur = head;
        virtual.next = cur;
        // 循环判断，如果相同就删除
        while(cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        return virtual.next;
    }
}

A. 环形链表II （⭐⭐⭐⭐）

为什么需要重置slow指针，然后每次一步就是入口点：

slow步长：slow = x + y

fast步长：fast = x + n (y + z) + y

fast=2 * slow

所以可以得出2x+2y = x + y + n (y + z) ⇒ x = (n - 1)(y + z) + z ⇒ x = y。经验得n=1

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 1. 特殊判断
        if(head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        // 2. slow 每次一步， fast 每次两步
        // 如果fast == null就是没有环
        do {
            slow = slow.next;
            if(fast == null) return null;
            fast = fast.next;
            if(fast == null) return null;
            fast = fast.next;
        }while(slow != fast);

        // slow回到起到，两个指针每次一步，相遇点就是入口
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}