力扣高频面试题解析：合并区间与相交链表

1. 项目概述力扣高频面试题精讲在技术面试备战过程中算法与数据结构始终是考察重点。今天我将拆解两道经典力扣题目56.合并区间数组类和160.相交链表链表类通过C实现演示如何系统化解决这类问题。这两道题分别位列力扣热题100榜单在近3年大厂面试中出现频率超过60%。2. 核心题目解析与解题思路2.1 力扣56.合并区间问题描述 给定一组区间合并所有重叠的区间。例如 输入[[1,3],[2,6],[8,10],[15,18]] 输出[[1,6],[8,10],[15,18]]关键解题步骤区间排序首先按照区间起始位置排序合并判断比较当前区间与结果集中最后一个区间的关系边界处理特别注意完全包含和部分重叠的情况vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vectorvectorint res; res.push_back(intervals[0]); for (int i 1; i intervals.size(); i) { if (res.back()[1] intervals[i][0]) { res.back()[1] max(res.back()[1], intervals[i][1]); } else { res.push_back(intervals[i]); } } return res; }2.2 力扣160.相交链表问题描述 编写一个程序找到两个单链表相交的起始节点。解题思路对比哈希表法O(mn)空间复杂度双指针法O(1)空间复杂度最优解ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *p1 headA; ListNode *p2 headB; while (p1 ! p2) { p1 p1 ? p1-next : headB; p2 p2 ? p2-next : headA; } return p1; }3. 核心算法深度剖析3.1 合并区间的时间复杂度分析排序阶段O(nlogn)线性扫描O(n)总体复杂度O(nlogn)注意当输入区间已经有序时可优化至O(n)3.2 相交链表的数学证明设链表A独立部分长为a链表B独立部分长为b公共部分长为c指针p1路径a c b指针p2路径b c a必然在第二轮的公共节点处相遇4. 面试实战技巧4.1 白板编码注意事项先明确输入输出边界条件口头说明算法思路再动手测试用例要覆盖空输入单个区间/节点完全包含/完全不重叠多重复合情况4.2 常见follow-up问题如果区间带权重如何合并如何检测链表存在环如果内存受限如何处理大数据量5. 每日练习建议建议练习顺序先独立实现基础解法然后尝试优化空间复杂度最后考虑各种边界case推荐关联题目57.插入区间141.环形链表142.环形链表II调试技巧// 打印区间向量 void printIntervals(const vectorvectorint intervals) { for (const auto interval : intervals) { cout [ interval[0] , interval[1] ] ; } cout endl; } // 打印链表 void printList(ListNode* head) { while (head) { cout head-val -; head head-next; } cout NULL endl; }6. 性能优化进阶6.1 合并区间内存优化// 原地修改输入数组 void mergeInPlace(vectorvectorint intervals) { sort(intervals.begin(), intervals.end()); int i 0; for (int j 1; j intervals.size(); j) { if (intervals[i][1] intervals[j][0]) { intervals[i][1] max(intervals[i][1], intervals[j][1]); } else { intervals[i] intervals[j]; } } intervals.resize(i 1); }6.2 相交链表异常处理ListNode* getIntersectionNodeWithCheck(ListNode *headA, ListNode *headB) { // 检查环存在 if (hasCycle(headA) || hasCycle(headB)) { throw invalid_argument(Linked list has cycle); } // 原解法... }7. 多语言实现对比7.1 Java版本关键区别// 合并区间 Listint[] merged new ArrayList(); merged.add(intervals[0]); // 注意Java的List操作API差异7.2 Python简洁实现# 合并区间 def merge(intervals): intervals.sort(keylambda x: x[0]) merged [] for interval in intervals: if not merged or merged[-1][1] interval[0]: merged.append(interval) else: merged[-1][1] max(merged[-1][1], interval[1]) return merged8. 实际工程应用场景合并区间典型应用会议室预定系统日程安排冲突检测带宽资源分配相交链表应用内存管理中的共享内存段文件系统的硬链接检测区块链的分叉合并9. 常见错误与调试方法合并区间易错点忘记先排序区间比较时漏掉等号修改结果集时未更新右边界相交链表调试技巧可视化两个链表结构添加循环次数计数器防死循环检查指针是否为nullptr// 调试示例 void debugIntersection(ListNode *headA, ListNode *headB) { int count 0; ListNode *p1 headA, *p2 headB; while (p1 ! p2 count 100) { // 防止无限循环 p1 p1 ? p1-next : headB; p2 p2 ? p2-next : headA; count; cout Step count : p1 (p1?p1-val:-1) , p2 (p2?p2-val:-1) endl; } }10. 扩展思考与变种题目合并区间的变种合并时保留最小N个区间带优先级的区间合并三维空间区间合并链表问题的延伸多链表交叉检测环形交叉链表动态变化的交叉链表在准备技术面试时建议每天保持3-5题的练习节奏重点不是刷题数量而是深入理解每道题目背后的算法思想。对于合并区间这类问题要特别注意边界的处理而链表问题则要多考虑指针操作的细节和特殊情况。