壁仞科技 AI Infra 实习 一面

发表于 更新于 分类于 ，

Q: 链表相交问题如何判断？

判断两个单链表是否相交（存在公共节点）：

方法一：双指针法（最优）：

  • 指针 A 从链表 A 头开始，指针 B 从链表 B 头开始
  • A 遍历完链表 A 后从链表 B 头继续；B 遍历完链表 B 后从链表 A 头继续
  • 如果相交：两指针会在交点相遇（各走 lenA + lenB - common 步）
  • 如果不相交：两指针都走完 lenA + lenB 步后同时到达 nullptr

原理：设 A 链表独有部分长 a，B 链表独有部分长 b，公共部分长 c。指针 A 走 a+c+b 步到达交点，指针 B 走 b+c+a 步到达交点。路径长度相同所以同时到达。

**时间 O(n+m)，空间 O(1)**。

方法二：将链表 B 尾部接到 A 头部形成环，用快慢指针判断是否有环。有环则相交。但会修改链表结构（需恢复）。

方法三：哈希集合。遍历 A 将所有节点存入 HashSet，再遍历 B 检查是否有节点在集合中。O(n+m) 时间 O(n) 空间。

Q: TopK问题：找最大的K个数用大根堆还是小根堆？

用小根堆（最小堆），堆大小固定为 K。

算法：

  1. 先将前 K 个元素建小根堆
  2. 遍历剩余元素：若当前元素 > 堆顶（堆中最小值），则替换堆顶并 heapify
  3. 遍历完成后堆中即为最大的 K 个数

为什么用小根堆而非大根堆：

  • 小根堆维护”当前最大 K 个数中的最小值”在堆顶，作为门槛——新元素超过这个门槛才有资格进入 top-K
  • 大根堆若要找 top-K，需要把所有 N 个元素放入后逐一弹出 K 次，空间 O(N) 且时间 O(N + K*logN)
  • 小根堆只需 O(K) 空间，时间 O(N * logK)

复杂度：时间 O(N * logK)，空间 O(K)。当 K << N 时远优于排序（O(N*logN)）。

其他方案：快速选择算法（QuickSelect）平均 O(N)，最坏 O(N^2)。适合一次性找第 K 大且不需要排序结果的场景。