AcWing 66. 两个链表的第一个公共结点
原题链接
简单
作者:
米多奇香米饼
,
2023-01-14 16:16:28
,
所有人可见
,
阅读 106
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
// auto p1=headA;
// auto p2=headB;
// while (p1 != p2) {
// if(p1 != NULL)//p1没有走到结尾
// p1 = p1->next;//p1指向下一个节点
// else//p1走到结尾
// p1 = headB;//p1指向另一个链表头
// if(p2 != NULL)//p2没有走到结尾
// p2 = p2->next;//p2指向下一个节点
// else //p2走到结尾
// p2 = headA;//p2指向另一个链表头
// }
// return p1;
auto p1=headA;
auto p2=headB;
int la=0;
int lb=0;
for(auto flag=headA;flag;flag=flag->next) la++;
for(auto flag=headB;flag;flag=flag->next) lb++;
int len=la-lb;
if(len<0){
len=lb-la;
p1=headB;
p2=headA;
}
while(len--) p1=p1->next;
while(p1){
if(p1==p2) return p1;
p1=p1->next;
p2=p2->next;
}
return nullptr;
}
};