题目链接👉 LeetCode 160.相交链表👈
💡题目分析
给你两个单链表的头节点 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;
}
🥰希望烙铁们能够理解欧!文章来源:https://www.toymoban.com/news/detail-652292.html
总结🥰
以上就是本题讲解的全部内容啦🥳🥳🥳🥳
本文章所在【C/C++刷题系列】专栏,感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远,也很暗,但是不要怕,不怕的人面前才有路。💕💕💕
小的会继续学习,继续努力带来更好的作品😊😊😊
创作写文不易,还多请各位大佬uu们多多支持哦🥰🥰🥰
文章来源地址https://www.toymoban.com/news/detail-652292.html
到了这里,关于LeetCode 160.相交链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!