桂林技术交流站,wordpress mu插件,wordpress app 开发,国外网站建设素材前言 相交链表是链表类面试的高频题#xff08;难度★★☆☆☆#xff09;#xff0c;核心考察对链表遍历、指针操作的理解。最初我用哈希表解决#xff0c;后续又学习了官方双指针法#xff0c;以及更易理解的「长度对齐法」#xff0c;三种解法各有优劣#xff0c;现…前言相交链表是链表类面试的高频题难度★★☆☆☆核心考察对链表遍历、指针操作的理解。最初我用哈希表解决后续又学习了官方双指针法以及更易理解的「长度对齐法」三种解法各有优劣现将完整思路、避坑点和复杂度分析整理如下。题目描述160. 相交链表 给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回null。注相交的定义是「节点地址相同」而非节点值相同。解法一哈希集合直观易想空间换时间核心思路利用哈希集合存储其中一个链表的所有节点再遍历另一个链表第一个在集合中匹配到的节点就是相交节点若遍历完未匹配说明无交点。实现代码/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode* nodeSet; // 存储链表A的所有节点 while(headA ! NULL){ nodeSet.insert(headA); headA headA-next; } // 遍历链表B查找相交节点 while(headB ! NULL){ if(nodeSet.find(headB) ! nodeSet.end()){ return headB; } headB headB-next; } return NULL; } };复杂度分析m、n分别为两个链表的长度时间复杂度O(mn)遍历链表 A 耗时 O(m)遍历链表 B 匹配耗时 O(n)空间复杂度O(m)需存储链表 A 的所有节点空间开销较大。解法二官方双指针法最优解核心思路两个指针分别从headA、headB出发遍历到链表末尾时跳转到另一个链表的头节点继续遍历。若链表相交两个指针会在相交节点处相遇移动总距离均为 mn若链表不相交两个指针最终都会指向NULL仍满足 pq直接返回即可。实现代码避坑版class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(headA NULL || headB NULL) return NULL; ListNode* p headA; ListNode* q headB; // 核心仅判断p!q允许p/q为NULL while(p ! q){ // 指针到末尾则跳转到另一链表头否则走next p p NULL ? headB : p-next; q q NULL ? headA : q-next; } // 最终pq要么是相交节点要么都是NULL return p; } };避坑要点重做这道题时曾写出「超时代码」核心错误// 错误代码核心问题 while (p ! NULL q ! NULL p ! q) { // 多余的非空判断 p p-next ! NULL ? p-next : headB; // 指针永远到不了NULL q q-next ! NULL ? q-next : headA; }循环条件加p!NULL q!NULL无交点时指针永远无法相等陷入死循环指针移动逻辑错误p-next!NULL导致指针永远到不了链表末尾无法跳转到另一链表违背双指针核心逻辑。复杂度分析m、n分别为两个链表的长度时间复杂度O(mn)最坏情况遍历两个链表所有节点空间复杂度O(1)仅使用两个指针变量常数级开销。解法三长度对齐法核心思路相交链表的「交点后长度」完全一致因此先计算两个链表的长度差让较长链表的指针先移动「长度差」步使两个指针到交点的距离一致再同步遍历第一个相等的节点即为交点。实现代码// 辅助函数获取链表长度 int GetLength(ListNode* head) { int len 0; while(head ! NULL) { len; head head-next; } return len; } ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { if (headA NULL || headB NULL) return NULL; int lenA GetLength(headA); int lenB GetLength(headB); ListNode* p headA; ListNode* q headB; // 较长链表的指针先移动长度差 while (lenA lenB) { p p-next; lenA--; } while (lenB lenA) { q q-next; lenB--; } // 同步遍历找第一个相等的节点 while (p ! NULL q ! NULL) { if (p q) return p; p p-next; q q-next; } return NULL; }复杂度分析m、n分别为两个链表的长度时间复杂度O(mn)计算长度遍历两次链表对齐后遍历一次最短链表空间复杂度O(1)仅使用长度变量和指针。三种解法对比解法时间复杂度空间复杂度优点缺点哈希集合O(mn)O(m)逻辑直观易实现空间开销大官方双指针O(mn)O(1)空间最优代码极简逻辑较抽象易踩死循环坑长度对齐法O(mn)O(1)逻辑易懂面试易口述需额外计算链表长度核心总结相交链表的核心是「节点地址相等」而非值相等最优解是官方双指针法需牢记「指针到末尾跳另一链表头 仅判断 p!q」的核心逻辑长度对齐法更适合面试口述哈希表法则适合快速实现可根据场景选择。