【初阶数据结构】——leetcode：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;
}