力扣Hot100-链表篇

链表类题目说到底其实就是修改结点的next与pre指针指向，说起来蛮简单的，但实操起来一不注意很容易就会出问题。
其中，快慢指针法可以帮助解决一系列链表类问题。
而在力扣 Hot100 上关于链表的题目数量挺多的，所以仅对一些比较令人头疼的问题进行总结。（依然是忽略 hard 难度题目）

160.相交链表

对于这道题，自己有想出两种不同的方式来解决：

• 利用 Set 集合，先将一个链表储存在其中，再遍历另一个链表，用于判断是否相交。
• 双重循环暴力解决。

这两种方式都无法满足题目，空间复杂度 O(1)，时间复杂度 O(n) 的要求，一种方法满足了空间复杂度，一种方法满足了时间复杂度，但不能兼之。
看了题解给出的最优解，我只能说，妙啊！

public class Solution {
    /**
     * 核心思想就是消除两个链表的长度差
     * 如何消除长度差？
     * 1.对于短链表，走到终点后，再走一遍长链表
     * 2.对于长链表，走到终点后，再走一遍短链表
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodeA = headA, nodeB = headB;

        while (nodeA != nodeB) {
            nodeA = nodeA == null ? headB : nodeA.next;
            nodeB = nodeB == null ? headA : nodeB.next;
        }

        return nodeA;
    }
}

234.回文链表🔥

花了一个小时想出来的 O(1) 空间复杂度最优解。
本以为官方题解有更优雅的解法，看了之后感觉大差不差，代码量还更大一些。
本质上就是先反转链表，然后再进行比较。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head.next == null) return true;

        ListNode nodeA = head;
        int size = 0;
        // 1.先求出链表长度
        while (nodeA != null) {
            size++;
            nodeA = nodeA.next;
        }
        
        // 2.遍历到中间靠右的那个结点
        int count = (size + 1) / 2;
        ListNode nodeB = head;
        for (int i = 0; i < count; i++) {
            nodeB = nodeB.next;
        }

        // 3.反转左边链表
        // 这里一定得注意分情况判断，防止在链表结点数为奇数的情况下，nodeA走到中间结点 
        if (size % 2 == 0) {
            nodeA = head;
            ListNode p = nodeA.next;
            head.next = null;
            while (p != nodeB) {
                ListNode temp = p.next;
                p.next = nodeA;
                nodeA = p;
                p = temp;
            }
        } else {
            nodeA = head;
            ListNode p = nodeA.next;
            head.next = null;
            while (p.next != nodeB) {
                ListNode temp = p.next;
                p.next = nodeA;
                nodeA = p;
                p = temp;
            }
        }

        // 4.进行判断
        while (nodeB != null) {
            if (nodeA.val != nodeB.val) return false;
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }

        return true;
    }
}

142.环形链表 Ⅱ

依然是使用快慢指针做，但涉及到了数学推导，和相交链表那题有异曲同工之妙。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null) {
            if (fast.next == null || fast.next.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        // 快慢指针第一次相遇后，让快指针回到起点
        fast = head;
        // 快慢指针同速移动，下一次相遇时即是环的入口
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }
}

24.两两交换链表中的结点

这道题有一点绕，不理清楚关系的话很容易就被绕进去了。
表明上来看是两个链表结点互相交换，实际上每次涉及到三个链表结点。

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 在头结点前再建立一个虚拟结点
        ListNode pre = new ListNode(0, head);
        ListNode temp = pre;
        while (temp.next != null && temp.next.next != null) {
            ListNode start = temp.next, end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next =start;
            temp = start;            
        }

        return pre.next;
    }
}

146.LRU 缓存

思路还是比较简单的，就是代码量不小。
使用哈希表建立 key 与 value 的映射关系，通过双向链表来记录 key 最近是否有使用。
怎么写这道题比较好呢？

1. 先把双向链表定义好；
2. 再定义一系列成员变量；
3. 写 put 与 get 方法；
4. 最后完善双向链表有关的操作。

class LRUCache {

    // 1.定义双向链表
    private class DListNode {
        private int key;
        private int val;
        private DListNode pre;
        private DListNode next;
        public DListNode() {}
        public DListNode(int key, int val) {
            this.val = val;
            this.key = key;
        }
    }

    // 2.定义一系列变量
    private int size;
    private int capacity;
    // 指向头结点，头部储存最近使用的
    private DListNode head;
    // 指向尾结点，尾部储存最近未使用的
    private DListNode tail;
    private Map<Integer, DListNode> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        size = 0;
        head = new DListNode();
        tail = new DListNode();
        head.next = tail;
        tail.pre = head;
        cache = new HashMap<>();
    }
    
    // 3.写put与get方法
    public int get(int key) {
        if (cache.containsKey(key)) {
            DListNode node = cache.get(key);
            // 移动至链表头部
            moveToHead(node);
            return node.val;
        }

        return -1;
    }
    
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            DListNode node = cache.get(key);
            node.val = value;
            moveToHead(node);
            return;
        }

        size++;
        DListNode node = new DListNode(key, value);
        cache.put(key, node);
        // 添加至链表头部
        addToHead(node);
        if (size > capacity) {
            // 移除尾结点
            node = removeTail();
            cache.remove(node.key);
            size--;
        }     
    }

    // 4.完善双向链表相关的方法
    private void addToHead(DListNode node) {
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    private void removeNode(DListNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void moveToHead(DListNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DListNode removeTail() {
        DListNode node = tail.pre;
        removeNode(node);
        return node;
    }
}

---

参考资料：
图解相交链表
环形链表 II（双指针，清晰图解）