鹰角网络9.19笔试AK复盘：奇偶链表、贪心与01trie

《面试题目》

1. 链表的奇偶重排：奇数节点仍放在奇数位置，偶数节点仍放在偶数位置。
2. 一道贪心题：从前往后贪心，每次尽可能取最小的区间；由于每个字母内部可以用除法快速计算，时间复杂度可做到 O(n)。
3. 统计区间异或和 ≤ k 的区间数量（01 trie 板子题）。

《参考解析》

奇偶链表重排：如果题意是「按节点下标的奇偶」分两条链（LeetCode 328），标准做法是两个哑结点 + 双指针：odd 串奇数位节点、even 串偶数位节点，遍历时交替挂链，最后 odd.next = evenHead，时间 O(n)、额外空间 O(1)。如果题意是「按节点值的奇偶决定落在哪个位置」，则先按值分成两条链再拼接，同样是 O(n)，但要注意稳定性——保持各自在原链表中的相对顺序，否则和期望输出对不上。作者说自己「用了点别的方法 100% 过了，估计不是正解」，通常就是把节点值抽出来排序再重建链表（O(n log n)、额外空间 O(n)），能过数据但面试官会追问能否 O(1) 空间。

贪心 + 除法优化：这类题的通用套路是从左往右扫，每次在当前限制下取「能取的最小区间」，因为区间越短，留给后面的余地越大——这是典型的区间调度式贪心（交换论证可证最优）。性能上如果一个个字符模拟会退化，而同一字符连续成段时可以用 剩余长度 / 段长 一次算出能跳过多少段，把均摊复杂度压到 O(字符串长度)。

区间异或和 ≤ k 的计数：核心两步。第一步做前缀异或 px[i] = a1 ^ a2 ^ ... ^ ai，于是区间 [l, r] 的异或和等于 px[r] ^ px[l-1]，问题转成「统计有多少对 i < j 使 px[i] ^ px[j] ≤ k」。第二步枚举右端点 j，把 px[0..j-1] 插入一棵 01 trie（每个节点维护子树内的计数），查询时从高位往低位贪心：若 k 的当前位为 1，则「异或该位为 0」的那棵子树里的所有数都满足 ≤ k，直接累加计数，然后走向「异或该位为 1」的子树继续判断；若 k 的当前位为 0，则只能走向异或结果为 0 的子树，否则这条分支全部不合法。遍历完所有位后把等于 k 的那一支也计入。总复杂度 O(n log V)，V 为值域。

两个容易挂掉的细节：一是数据类型，异或和的上界取决于 a[i] 的位宽，若 a[i] 最大到 1e9（30 位）则前缀异或仍在 int 范围内，但如果涉及求和或 a[i] 接近 2^31 就必须用 long long；二是「区间」是否允许长度为 1、是否包含空区间，l = 1 时需要用到 px[0] = 0，插入顺序必须是「先查后插」还是「先插后查」取决于题目是否允许 l = r。