朋友们、伙计们，我们又见面了，本期来给大家解读一下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;
}