HOT100：链表

19 相交链表 ⭐

链表中的经典题

当我在我的路上走过一遍依然没有遇见你时，那么我会接着来到你走过的路走一遍，而你如果也和我一样心有灵犀，那么总有一天我们将在合适的时候相遇。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode p = headA;
    ListNode q = headB;
    while (p != q){
        p = p == null ? headB : p.next;
        q = q == null ? headA : q.next;
    }
    return p;
}

• 空间复杂度 O(1)

20 反转链表 ⭐

迭代版本如下，循环结束时，cur = null，pre 是头节点。

public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null){
        ListNode nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

递归版本：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null){
        return head;
    }
    // 向下递归，拿到链表的头节点
    ListNode p = reverseList(head.next);
    // 反转当前节点
    head.next.next = head;
    head.next = null;
    // 返回头节点
    return p;
}

21 回文链表

题目进阶要求 O(1) 的空间复杂度，因此可以反转一半的链表，然后同时遍历判断是否回文。

如何查找链表的中心节点呢？可以通过快慢指针：876. 链表的中间结点

public boolean isPalindrome(ListNode head) {
    ListNode mid = middleNode(head);
    ListNode h2 = reverse(mid);
    while (h2 != null){
        if (h2.val != head.val){
            return false;
        }
        h2 = h2.next;
        head = head.next;
    }
    return true;
}

// 链表的中间节点
public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

// 反转链表
public ListNode reverse(ListNode head){
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null){
        ListNode nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

22 环形链表

141. 环形链表

题目进阶要求 O(1) 的空间复杂度，可以使用快慢指针解决。

如果有环的话，那么兔子和乌龟都会进入环中。这时用「相对速度」思考，乌龟不动，兔子相对乌龟每次只走一步，这样就可以看出兔子一定会和乌龟相遇了。

public boolean hasCycle(ListNode head) {
    // 乌龟和兔子同时从起点出发
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null){
        slow = slow.next;       // 乌龟走一步
        fast = fast.next.next;  // 兔子走两步
        // 如果有环，兔子会套圈追上乌龟
        if (slow == fast){
            return true;
        }
    }
    return false;
}

26 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点

双指针做法：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode left = dummy;
    ListNode right = dummy;
    // 右指针先走 n 步
    for (int i = 0; i < n; i++){
        right = right.next;
    }
    // 左右指针一起走
    while (right.next != null){
        left = left.next;
        right = right.next;
    }
    // 删除倒数第 n 个节点
    left.next = left.next.next;
    return dummy.next;
}

27 两两交换链表中的节点

32 LUR 缓存 ⭐

本题使用双向链表实现：

• get：把节点抽出来，放到链表头部

• put：如果已经存在就抽出来放到头部并更新val，否则直接插入链表头部

使用哈希表快速根据 key 获得节点。

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;

        Node(int k, int v) {
            key = k;
            value = v;
        }
    }

    private final int capacity;
    private final Node dummy = new Node(0, 0); // 哨兵节点
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.next = dummy;
        dummy.prev = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node == null ? -1 : node.value;
    }

    // 获取 key 对应的节点，同时把该节点移到链表头部
    private Node getNode(int key) {
        if (!keyToNode.containsKey(key)) {
            return null;
        }
        Node node = keyToNode.get(key);
        remove(node);
        addFirst(node);
        return node;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        // 已经存在，直接修改值
        if (node != null) {
            node.value = value;
            return;
        }
        // 插入链表头部，并更新哈希表
        node = new Node(key, value);
        addFirst(node);
        keyToNode.put(key, node);
        // 达到容量上限，则删除最后一个节点
        if (keyToNode.size() > capacity) {
            Node last = dummy.prev;
            remove(last);
            keyToNode.remove(last.key);
        }
    }

    // 删除一个节点
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 在链表头添加一个节点
    private void addFirst(Node node) {
        node.prev = dummy;
        node.next = dummy.next;
        node.prev.next = node;
        node.next.prev = node;
    }
}