日野弥生：勉強しよう
LeetCode 160 - 相交链表
发表于2025年01月15日
由于要求不能改变链表的结构，通过观察得知，尾部如果相交，则双指针的起点必须保证步数一致，这是解题的关键。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* Ap=headA, *Bp=headB;
int A_len=0,B_len=0;
while(Ap->next)
{
Ap=Ap->next;
A_len++;
}
while(Bp->next)
{
Bp=Bp->next;
B_len++;
}
/* 求出双方长度后，让双指针的起点调整，保证遍历时步数一致 */
Ap=headA,Bp=headB;
if(A_len>B_len)
{
while(A_len-B_len>0)
{
Ap=Ap->next;
A_len--;
}
}
else if(A_len < B_len)
{
while( A_len-B_len < 0)
{
Bp=Bp->next;
B_len--;
}
}
/* 步数一致时，如果相等了那就一定相交*/
while(Ap!=Bp)
{
Ap=Ap->next;
Bp=Bp->next;
}
return Ap;
}
};