9.19鹰角网络笔试：三道算法题速记

《面试题目》

1. 奇偶链表重排
2. 一道贪心算法题（从左往右模拟即可）
3. 01 trie

《参考解析》

奇偶链表重排：把链表按「奇数位节点 / 偶数位节点」拆成两条链再拼接，是 O(n) 时间、O(1) 空间的标准做法——用两个哑结点分别串 odd 与 even，遍历时交替挂链，最后把偶数链接到奇数链尾部。如果用数组抽出所有节点值再排序重建，能过数据但是 O(n log n) 且需要额外空间，面试时容易被追问优化。实现时要特别注意链表长度为 0/1 的边界，以及断开与拼接的顺序（先保存 evenHead 再改指针）。

从左往右的贪心模拟：这类题的通用判断是「每一步选当前最优是否不留后患」。典型做法是从左端出发，维护当前状态（已覆盖位置、剩余资源），每次尽量取最小的可行区间，用前缀和或计数把「能不能取」的判定压到 O(1)。能贪心的证明一般是交换论证：若最优解在某一步取了更大的区间，把它替换成更小的不会让后续更差。若换成同字符连续段，可以用除法一次跳过整段，避免逐字符模拟。

01 trie 题：一般是「区间异或和 ≤ k 的区间数量」「最大异或对」「异或第 k 大」这一类。以区间异或和为例：先求前缀异或 px[i]，区间异或和变成 px[r] ^ px[l-1]，问题转成「统计有多少对 i < j 满足 px[i] ^ px[j] ≤ k」；枚举右端点，把之前的前缀异或值插进 01 trie（节点维护子树计数），查询时从高位往低位贪心——k 当前位为 1 时，异或结果为 0 的子树全部合法（整棵累加），再走 1 的那侧；为 0 时只能走异或结果为 0 的一侧。复杂度 O(n log V)。

笔试节奏提醒：三道题全 AK 的关键在于识别题型——链表题想 O(1) 空间的双指针、模拟题先想能不能贪心、异或题直接反应到 01 trie / 线性基。把这几类模板练到能默写，笔试就只剩读题和边界处理了。