之前开过一个坑 Leetcode 刷题笔记，总结了许多 Leetcode 上的好题。然而，这些题还是比较乱的，不利于我们备考和面试。因此，我选择新开一个坑，专门记录 Leetcode 上的各种模板题，从而帮助我们更好地复习。

1. 链表题

1.1 第160题.相交链表

参考题解：官方题解

题目：

标签：

• 哈希表。
• 双指针。

思路：

• 这道题的挑战在于，如何将时间复杂度降到 O(n)，空间复杂度降到 O(1)。
• 看到时间复杂度 O(n) 基本就明白了，方法被限制在了：哈希表、双指针、位运算。这个敏感性还是需要具备的。
• 用哈希表求解可以实现 O(n) 的空间复杂度。
• 用双指针求解才是最优解。而这个思路还有一些特别，需要记住：指针 A 扫描到 A 串末尾后，需要跳到 B 串。B 到末尾也要跳到 A 串。比较指针指向的节点是否相等，不能光判断 val，还需要判断 next，因此可以直接判断指向的节点是否相等（==）。

题解：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode val1 = headA, val2 = headB;
        if (val1 == null || val2 == null) {
            return null;
        }
        while (true) {
            if (val1 == null && val2 == null) {
                return null;
            }
            if (val1 == null) {
                val1 = headB;
            }
            if (val2 == null) {
                val2 = headA;
            }
            if (val1 == val2) {
                return val1;
            }
            val1 = val1.next;
            val2 = val2.next;
        }
    }
}

2. 其他题

2.1 第401题. 二进制手表

参考题解：官方题解

题目：

标签：

• 意想不到。
• 位运算。

思路：

• 这道题是一道简单题，只需要枚举就可以解决。
• 然而，必须要知道这是一道枚举题。否则可能会想歪。
• 枚举所有数字，用 bitCount 计算对应的比特数，保留符合要求的组合，并生成符合格式要求的题解。

题解：

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<String>();
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    ans.add(h + ":" + (m < 10 ? "0" : "") + m);
                }
            }
        }
        return ans;
    }
}