单链表经典例题：相交链表 你一看就会

力扣的题目链接原题https://leetcode.cn/problems/intersection-of-two-linked-lists/给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回null。图示两个链表在节点c1开始相交两个问题是否相交交点在哪。是否相交如果两个链表的最后一个节点 不是同一个 → 不相交如果最后一个节点 是同一个 → 一定相交原理超级重要相交的链表一定会共用最后一个节点就像两条路最后汇成一条路终点一定一样。交点在哪1. 先让长链表先走几步对齐长度2. 两个指针再一起走3.第一次相遇的地方 交点代码展示/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ // 功能找到两个单链表的相交节点找不到返回 NULL struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { // 定义两个指针 p1 走链表Ap2 走链表B struct ListNode*n1 headA,*n2 headB; // 用来记录两个链表的长度 int a1 0,a2 0; // // 第一步遍历链表 A走到最后一个节点同时算长度 // while(n1-next) // 注意你写的是走到倒数第一个节点就停 { n1 n1-next; a1; } // // 第二步遍历链表 B走到最后一个节点同时算长度 // while(n2-next) // 同样走到倒数第一个停 { n2 n2-next; a2; } // // 第三步最重要判断两个链表是否相交 // // 如果相交**最后一个节点一定是同一个节点** // 如果不是同一个直接返回 NULL不可能相交 if(n1!n2) return NULL; // // 第四步重置指针回到头部修正长度 // n2 headB; // n2 回到 B 头 n1 headA; // n1 回到 A 头 a1; // 刚才少算了最后一个节点补上 a2; // 同上 // // 第五步让 n1 永远指向 **更长** 的那个链表 // if(a1 a2) { n1 headB; // 长链表给 n1 n2 headA; // 短链表给 n2 } // // 第六步计算长度差取绝对值保证是正数 // int n a1 - a2; if(n 0) n -n; // // 第七步长链表的指针 **先走 n 步** // 让两个指针“对齐”剩下的长度一样 // while(n--) { n1 n1-next; } // // 第八步两个指针同时走 // 相遇的地方 相交节点 // while(n1) { if(n1 n2) // 地址相同 相交 return n1; // 直接返回节点 n1 n1-next; // 同时走 n2 n2-next; } // 最终没找到返回空 return NULL; }常见问题1. 为什么要走到最后一个节点相交链表的终极特征最后一个节点一定是同一个如果两个链表尾巴不一样 →绝对不相交你代码直接return NULL非常聪明2. 为什么要算长度因为两个链表一长一短不能直接一起走。必须让长的先走几步把长度补齐。3. 为什么长链表要先走 n 步目的让两个指针站在 “同一起跑线”对齐后两个指针同时走一定会同时到达交点。4. 为什么比较 n1 n2而不是比较值比较的是节点地址交点是同一个节点不是值相同只有地址一样才是真的相交