相交链表（c语言）

思路一：通过快慢指针消除两个链表的距离差，长的先走差距步再同时走，第一个相等就是交点

注意的点：差距步通过两个链表的长度之差得到，其次像这种不知道哪个链表更长时我们可以使用假设法

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB){
struct ListNode* curA = headA, *curB = headB;
int lenA = 1,lenB = 1;
while(curA->next)
{
curA=curA->next;
lenA++;
}
while(curB->next)
{
curB=curB->next;
lenB++;
}
//尾结点不相等就是不相交
if(curA != curB)
{
return NULL;
}
//长的先走差距步，再同时走，第一个相等就是交点
//假设法
int gap=abs(lenA – lenB);
struct ListNode* longList = headA, *shortList = headB;
if(lenB > lenA)
{
longList = headB;
shortList = headA;
}
while(gap–){
longList = longList->next;}

while(longList != shortList){
longList = longList->next;
shortList = shortList->next;}
return shortList;
}