原题链接:力扣面试题02.07.链表相交
思路
两个长度不确定是否一致的链表,如果相交,那么一定是有一个链表结点相同,注意不是值相同而是结点相同,也就代表了是需要指针是相同的才行
根据图可以得出,相交后的结点都是一致的,那么需要做的就是把两个链表长度统一,再从头结点逐步遍历,直至指针结点相同,返回相同的指针结点即可
如果没有相同的指针结点 则代表没有相交 返回NULL文章来源:https://www.toymoban.com/news/detail-739588.html
全代码:文章来源地址https://www.toymoban.com/news/detail-739588.html
/**
* 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) {
//遍历headA链表和headB链表的长度
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0,lenB = 0;
while(curA != NULL)
{
curA = curA ->next;
lenA++;
}
while(curB != NULL)
{
curB = curB ->next;
lenB++;
}
if(lenB > lenA)
{//需要让lenA成为长度最长的链表
swap(lenA,lenB);
swap(headA,headB);
}
int len = lenA - lenB;
while(len--)
{
headA = headA ->next;
}
curA = headA;
curB = headB;
while(curA != NULL)
{
if(curA == curB)
{
return curA;
}
curA = curA ->next;
curB = curB ->next;
}
return NULL;
}
};
到了这里,关于力扣面试题02.07.链表相交的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!