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

1. 链表题

1.1 第160题.相交链表

参考题解:官方题解

题目:

image-20210604091505091

标签:

  • 哈希表。
  • 双指针。

思路:

  • 这道题的挑战在于,如何将时间复杂度降到 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;
        }
    }
}