本文主要是介绍相交链表(Leetcode)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目分析：
. - 力扣（LeetCode）
相交链表：首先我想到的第一个思路是：如图可知，A和B链表存在长度差，从左边一起遍历链表不好找交点，那我们就从后面开始找，但是这是单链表，没有 prev 指针，所以只能反转链表 A、B。反转之后再从A、B头结点开始就可以找到相遇点，但是题目要求我们不能改变链表的结构，所以此方法不行。
方法一：
思路：
①当链表有一个为空，或者两个都为空的时候，直接返回NULL。
②因为链表存在差值，结点个数不同，不能一起遍历，所以我们可以求出A和B各自的结点个数，然后求出差值。
③差值有了之后，我们可以让长的链表先走差值步，相对于抹掉了差值。
④最后A、B链表一起走，如果地址相等就表示相遇了，就返回交点处的地址，如果没有相遇，就返回NULL
struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {struct ListNode* curA = headA;struct ListNode* curB = headB;if (curA == NULL || curB == NULL)return NULL;//求链表A、B各自的长度int la = 0;int lb = 0;while (curA) {curA = curA->next;++la;}while (curB) {curB = curB->next;++lb;}//找到两个链表中较长的那个struct ListNode* longest = headA;struct ListNode* shortest = headB;if (la < lb) {longest = headB;shortest = headA;}//求出差值，然后先让长的链表走完差值int gap = abs(la - lb);while (gap--) {longest = longest->next;}//同时出发，直到相遇，否则没有相遇while (longest) {if (longest == shortest)return longest;longest = longest->next;shortest = shortest->next;}return NULL;
}
方法二：
思路：
①当链表有一个为空，或者两个都为空的时候，直接返回NULL。
②相当于两个指针在一个路线上走、走的路程都是一样的
A先走完自己的路程，然后去走B的路程
B先走完自己的路程，然后去走A的路程
A和B走到路一样长
如果存在相遇点，A和B必定会相遇 (如果不是很明白可以对着代码，画图去理解一下)
如果不存在相遇点，就在NULL处相遇
struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {if (headA==NULL || headB==NULL){return NULL;}struct ListNode* A = headA;struct ListNode* B = headB;while (A != B) {A = A ? A->next : headB; B = B ? B->next : headA;}return A;
}
这篇关于相交链表(Leetcode)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
