题目描述
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
示例
解题思想
将两个链表从尾部对齐,然后进行寻找。
此时我们就可以比较curA和curB是否相同,如果不相同,同时向后移动curA和curB,如果遇到curA == curB,则找到交点。
切记:不是curA->val==curB->val
代码
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
int lenA=0, lenB=0;
ListNode* curA = headA, * curB = headB;
while (curA) {
lenA++;
curA = curA->next;
}
while (curB) {
lenB++;
curB = curB->next;
}
//将两个链表从尾部对其
curA = headA;
curB = headB;
int gap;
if (lenA >= lenB) {
gap = lenA - lenB;
for (int i = 0; i < gap; i++) {
curA = curA->next;
}
}
else {
gap = lenB - lenA;
for (int i = 0; i < gap; i++) {
curB = curB->next;
}
}
while (curA && curB) {
if (curA == curB)
return curA;
else {
curA = curA->next;
curB = curB->next;
}
}
return NULL;
}
};