/**
* 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) {
// 先对齐尾部,因为如果有相交的结点,那么尾部那一段都是重复的
ListNode* curA = headA;
ListNode* curB = headB;
// 各自求两个链表的长度
int lenA = 0, lenB = 0;
while(curA!=NULL){
lenA++;
curA = curA->next;
}
while(curB!=NULL){
lenB++;
curB = curB->next;
}
// 末尾对齐
int abs = (lenA-lenB); // 两者长度之差
if(abs>=0){
curA = headA;
curB = headB;
}else{
abs = -abs; // 小于零取相反数
curA = headB;
curB = headA;
}
// 现在curA默认指向长的链表 curB默认指向短的链表
while(abs--){
curA = curA->next;
}
// 现在相当于尾部对齐了,接下来只要有一个元素地址相同,那么后面的地址都相同了
while(curA!=NULL){
if(curA==curB){
return curA;
}else{
curA = curA->next;
curB = curB->next;
}
}
return NULL;
}
};