如果两个链表相交，又都不存在环，那么不难想象这两个链表共同构成了一个Y型,相交部分全部都相同，两链表交点处指针相等。
声明指针A指向链表A的头结点，指针B指向链表B的头结点。
我们求出两个链表的长度，并求出两个链表长度的差值gap。
让两个链表末尾对齐，指向长链表的指针移动gap个位置。
此时我们就可以比较指针A和指针B是否相同，如果不相同，俩指针同时向后移动1个next，如果相同，则找到交点。
否则循环退出返回空指针。
class Solution
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode *curA = headA; //指针A
ListNode *curB = headB; //指针B
int lenA = 0;
int lenB = 0;
while (curA!=NULL) //求链表A的长度
{
lenA++;
curA = curA->next;
}
while (curB!=NULL) //求链表B的长度
{
lenB++;
curB = curB->next;
}
//指针重新指向头结点
curA = headA;
curB = headB;
//设curA为最长链表的头,如果链表B的长度大于A，就把curA和curB交换，链表A和B的长度交换
if (lenB>lenA)
{
swap(lenA, lenB);
swap(curA, curB);
}
//求长度差
int gap = lenA - lenB;
//两个链表末尾位置对齐
while (gap--)
{
curA = curA->next;
}
//遍历两个链表，遇到相同的直接返回结点
while (curA!=NULL)
{
if (curA==curB)
{
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
时间复杂度度O(n+m)
空间复杂度O(1)
附代码运行结果:
