力扣160.相交链表
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
思路分析
首先明确题目所要求的：
1.两链表是否相交？
2.如果相交的话，交点在哪？
首先解决第一个问题，判断是否相交。首先两个链表的头结点可能一样也可能不一样，但如果相交的话，它们的尾结点一定是同一个，那么我们可以分别遍历这两个链表到尾，如果一样的话就代表它们一定相交，否则直接返回false。
到第二个问题，找交点，如果俩链表同时从头遍历，再找它们相同的结点的话，那么当俩链表长度不同，指针就会错位，这是不靠谱的做法，正确的做法是，将它们遍历的起点进行统一后再进行遍历，直到碰到相同的结点，就是它们的交点。
如何统一起点呢？
首先找出较长链表，将俩链表长度的差当作步数，让长链表的指针先走完这些步数，这样两个链表的指针就统一了，之后两个指针再一起遍历，直到碰到相同结点停止，返回任意一个指针即是对应的交点。
完整代码
代码语言：javascript复制/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* curA=headA,*curB=headB;
int lenA=1,lenB=1;//从1开始。
while(curA)
{
lenA ;
curA=curA->next;
}
while(curB)
{
lenB ;
curB=curB->next;
}
if(curA!=curB)/判断是否相交
{
return NULL;
}
int n=abs(lenA-lenB);
struct ListNode* longlist=headA,*shortlist=headB;//可以先假设其中一个为长链表。
if(lenB>lenA)//如果不是在交换即可。
{
longlist=headB;
shortlist=headA;
}
while(n--)//长指针先走
{
longlist=longlist->next;
}
while(shortlist!=longlist)//两个一起走，直到相同停下
{
shortlist=shortlist->next;
longlist=longlist->next;
}
return longlist;//返回其中任意一个即可。
}实现细节
注意比较的是该节点而非该节点的值，因为链表是乱序且无规律的。
