【初阶数据结构】——160. 相交链表
1. 题目介绍
链接: link
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
2. 思路1：暴力求解
算法思想
首先第一种思路就是暴力求解，这可能是我们最容易想到的：
让A链表的每个结点依次与B中所有结点逐个比较（拿B的跟A比也是一样），当然这里要注意比较的时候应该比较结点的地址，而不应该比较结点的值。结点的值一样并不能证明它们相交。 这种方法思想很简单，但是效率不好，这样的话时间复杂度就是
O（N^2）
代码实现
代码也很简单，可以给大家写一下：
也可以通过。
//暴力求解，让A链表的每个结点依次与B中所有结点逐个比较。O（N^2）
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
struct ListNode* curA = headA;
struct ListNode* curB = headB;
while (curA)
{
curB=headB;
while (curB)
{
if (curA == curB)
return curA;
curB = curB->next;
}
curA = curA->next;
}
return NULL;
}但是上面的算法效率不是很好，我们能不能优化一下呢？
3. 思路2：快慢指针
算法思想
大家思考一个问题：
上面我们暴力比对结点的地址来寻找链表的交点。 但是为什么要拿A链表的每个结点依次与B中所有结点逐个比较呢？ 为什么不能同步的遍历两个链表，比较对应的结点呢？ 如果同步遍历话，就是
O（N）了 ?，不能直接这样，因为两个链表的长度可能是不一样的。 比如像这样
如果我们同步的遍历去比对，显然是不行的，不能得到正确的结果。
那不能直接同步遍历两个链表的去比较，我们能不能想个办法让他们可以同步遍历去比较呢？
我们来分析一下。 如果两个链表相交，但是长度不相等，那么不相等的部分一定是在交点之前的。 因为相交之后它们后面的结点都是一样的嘛。
那上面我们分析了，就是因为两个链表的长度可能不一样，所以不能同步遍历去比较。 那我们能不能把他们变成一样长呢？ ?，我们可以这样做
我们可以同步遍历去比较。 但是，如果长度不相等，我们要先让较长的那个链表的遍历指针先走长度的差值步
此时，我们看到，是不是就可以让curA和curB同时往后走，比较对应的结点了。
这样如果它们有交点的话，就一定会出现curA==curB，此时这两个指针指向的结点就是第一个交点，返回curA或curB都可。 如果没有交点，那就一直往后走curA不会和curB相等，遍历结束，curA和curB都走到空，返回curA或curB都可。（当然待会大家看我们的代码，不相交的话我们在求长度差值的时候其实就能判断出来了）
所以：
我们可以先遍历一遍两个链表，求出它们的长度，判断出谁长谁短，并计算出长度的差值。 然后让长的链表先走差值步，再同步往后走，比较对应结点，找交点。
代码实现
理清了思路，我们来写一下代码：
提交一下：
过啦！
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *curA=headA;
struct ListNode *curB=headB;
int lenA=0;
int lenB=0;
//找尾，先判断是否相交，不相交直接返回NULL，相交再找
while(curA->next)
{
lenA++;
curA=curA->next;
}
//计算准确长度应该这样写：while(curA)
//这样while(curA->next)比实际长度小1，但是两个都小1，不影响差值
//而这样写循环结束cur就是尾，可直接判断是否相交
while(curB->next)
{
lenB++;
curB=curB->next;
}
//尾不相等，则不相交
if(curA!=curB)
return NULL;
//计算差值
int gap=abs(lenA-lenB);
//找出长的那一个
struct ListNode *longlist=headA;
struct ListNode *shortlist=headB;
if(lenB>lenA)
{
longlist=headB;
shortlist=headA;
}
//长表先走差值步
while(gap--)
{
longlist=longlist->next;
}
//再一起走，比较两个链表的当前结点是否相同
//，第一个相同的就是第一个交点
while(longlist!=shortlist)
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;
}