💡题目分析
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
💡解题思路
🚩步骤一：找尾节点
struct ListNode* tailA = headA; struct ListNode* tailB = headB; int lenA = 1,lenB = 1; while(tailA) { tailA = tailA->next; lenA++; } while(tailB) { tailB = tailB->next; lenB++; }
🚩步骤二：判断尾节点是否相等
判断尾节点是否相等，如果尾节点相等就是相交
if (tailA != tailB) { return NULL; }
🚩步骤三：找交点
🍄思路1
A链表所有节点跟B链表都比较一遍，相等的那个就是交点
这种暴力求解法解决这道题是没问题的。但是这种解法时间复杂度为 O(N^2) / O(N*M)，要求优化到 O(N)，所以我们不采用这种暴力解法，建议使用下一种解法👇
🍄思路2
分别定义两个链表的长度 lenA 和 lenB，长的先走abs(lenA - lenB)步（差距步），然后再同时走，第一个相等的就是相交节点
//长的先走差距步 int gap = abs(lenA - lenB); //abs函数是对整数进行取绝对值 struct ListNode* longList = headA; struct ListNode* shortList = headB; if(lenA < lenB) { longList = headB; shortList = headA; } while(gap--) { longList = longList->next; } while(longList != shortList) { longList = longList->next; shortList = shortList->next; }
👇图解👇
此方法整体时间复杂度为：O(M+N) / O(N)，空间复杂度为：O(1)
🔔接口源码
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* tailA = headA; struct ListNode* tailB = headB; int lenA = 1,lenB = 1; while(tailA) { tailA = tailA->next; lenA++; } while(tailB) { tailB = tailB->next; lenB++; } //判断最后一个节点是否相等（是否相交） if(tailA != tailB) { return NULL; } //长的先走差距步 int gap = abs(lenA - lenB); struct ListNode* longList = headA; struct ListNode* shortList = headB; if(lenA < lenB) { longList = headB; shortList = headA; } while(gap--) { longList = longList->next; } //一一对应比较，判断重叠节点(因为前面已经经过是否相交的判断，所以执行至此，必定是相交的) while(longList != shortList) { longList = longList->next; shortList = shortList->next; } //二者相等，任意一一个都是相交起始点 return longList; }
🥰希望烙铁们能够理解欧！
总结🥰
以上就是本题讲解的全部内容啦🥳🥳🥳🥳
本文章所在【C/C++刷题系列】专栏，感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远，也很暗，但是不要怕，不怕的人面前才有路。💕💕💕
小的会继续学习，继续努力带来更好的作品😊😊😊
创作写文不易，还多请各位大佬uu们多多支持哦🥰🥰🥰
