力扣160.相交链表
题目描述
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
思路分析
首先明确题目所要求的:
1.两链表是否相交?
2.如果相交的话,交点在哪?
首先解决第一个问题,判断是否相交。首先两个链表的头结点可能一样也可能不一样,但如果相交的话,它们的尾结点一定是同一个,那么我们可以分别遍历这两个链表到尾,如果一样的话就代表它们一定相交,否则直接返回false。
到第二个问题,找交点,如果俩链表同时从头遍历,再找它们相同的结点的话,那么当俩链表长度不同,指针就会错位,这是不靠谱的做法,正确的做法是,将它们遍历的起点进行统一后再进行遍历,直到碰到相同的结点,就是它们的交点。
如何统一起点呢?
首先找出较长链表,将俩链表长度的差当作步数,让长链表的指针先走完这些步数,这样两个链表的指针就统一了,之后两个指针再一起遍历,直到碰到相同结点停止,返回任意一个指针即是对应的交点。
完整代码
/**
* 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;//返回其中任意一个即可。
}
实现细节
注意比较的是该节点而非该节点的值,因为链表是乱序且无规律的。