朋友们、伙计们，我们又见面了，本期来给大家解读一下LeetCode中第160道单链表OJ题，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！
数据结构与算法专栏：数据结构与算法
个 人 主 页 ：stackY、
C 语 言 专 栏：C语言：从入门到精通
LeetCode--160.相交链表：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
目录
1.题目介绍
2.实例演示
3.解题思路
1.题目介绍
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
2.实例演示
3.解题思路
链表相交有一种别的说法叫做公共节点，但是不能吧链表相交理解为链表交叉，在我们学的链表结构中还不存在这种交叉的结构，因为每一个节点的next只有一个，不会有两个甚至更多，因此链表相交的结构得搞清楚。
如果我们仔细观察相交链表的特点，我们不难发现相交的两个链表的尾结点是一样的，因此在找两个单链表相交的起始节点的前提是两个链表必须相交，所以我们可以先判断两个链表的尾结点是否相等，如果不相等，那么直接返回NULL即可。所以需要遍历链表找尾节点。
判断完链表是否相交之后我们该咋找两个单链表相交的起始节点呢？
这里有两种方法：
1. 暴力求解法：
将A链表的所有结点于B链表的所有结点依次进行比较，直到找到相等的结点。
但是这种方法太麻烦，代价比较大，时间复杂度为O(N*M)。要寻求其他解决办法。
2. 差距步法：
小编在这里给大家推荐一个比较简单的方法：分别求出两个链表的长度，然后较长的链表先走它们长度的差距步，然后两个链表再一起走，当两个链表相等就是相交点。因此我们可以在找两个链表的尾结点时顺便求出它们各自的长度。时间复杂度为O(N)。
在这里还要注意的一个点就是如何求出最长的链表，这里推荐使用假设法，假设A链表最长，然后判断A和B的长度，不符合条件就交换B为长链表，这样做的目的是代码不会冗余。
总结：
要求相交链表最简便的方法：
1. 先分别找两个链表的尾结点，并且分别求出两个链表的长度然后判断两个链表的尾结点是否相等，不相等则没有相交。
2. 若相等，则证明相交，此时找出最长的链表，让最长的链表先走它们两个链表长度的差距步，然后两个链表再一起走，走到相等的时候，则是两个链表的相交点。
代码演示：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* tailA = headA;
struct ListNode* tailB = headB;
int lenA = 1;
int lenB = 1;
//找A链表的尾结点并且求出链表的长度
while(tailA->next)
{
tailA = tailA->next;
lenA++;
}
//找B链表的尾结点并且求出链表的长度
while(tailB->next)
{
tailB = tailB->next;
lenB++;
}
//判断是否相交
if(tailA != tailB)
return NULL;
//求出它们长度的差距
int gap = abs(lenA - lenB);
//找出最长的链表
struct ListNode* longlist = headA;
struct ListNode* shortlist = headB;
if(lenA < lenB)
{
longlist = headB;
shortlist = headA;
}
//长的先走差距步
while(gap--)
{
longlist = longlist->next;
}
//再一起走，直到相等
while(longlist != shortlist)
{
longlist = longlist->next;
shortlist = shortlist->next;
}
return longlist;
}
朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！
文章来源
您阅读本篇文章共花了：
发表评论