本文主要是介绍链表OJ----相交链表找交点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
1、长链表先走，然后二者一起走
由于两个链表可能不一样，就不好控制移动。那么我们可以让长的链表先走二者的长度差的长度，使剩下部分和短链表一样长。然后二者一起走动，去寻找交点。
struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {if (headA == NULL || headB == NULL)return NULL;int lenA = 1,lenB =1; //记录长度，由于二者此时不为空链表，并且我们要找到最后一个结点，而不是空结点，所以这里起始长度为1struct ListNode *pa = headA, *pb = headB;while (pa->next != NULL) //找最后一个结点{lenA++;pa = pa->next;}while (pb->next != NULL) //找最后一个结点{lenB++;pb = pb->next;}if (pa != pb) //判断最后一个结点是否相等return NULL;int dis = abs(lenA - lenB);if (lenA > lenB) // A走{while (dis > 0) {headA = headA->next;dis--;}} else // B走{while (dis > 0) {headB = headB->next;dis--;}}//一起走while (headA != headB) {headA = headA->next;headB = headB->next;}//如果找到就返回headA//如果没找到，那么二者最终都为NULLreturn headA;
}2、逆置链表
虽然题目说不能改变链表结构，但逆置链表也是一种办法，我们可以参考。代码就不写了，看看分析图即可。
3、双指针法
下面我们来验证一下思路是否正确：
假设headA长为a，headB长为b：
情况1：假设a == b，pa和pb都走了x的长度（x<a），此时pa == pb != NULL，则交点找到；假设pa和pb都走了a的长度，此时pa == pb == NULL，则没有交点。
情况2：假设a!=n，pa先走了a，再走x（x<b），pb先走了b，再走y(y<a)，此时pa == pb != NULL，则交点找到；如果x == b，y == a，则pa走了a+b，pb走了a+b，此时pa == pb == NULL，则没有交点。
struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {if (headA == NULL || headB == NULL)return NULL;struct ListNode *pa = headA, *pb = headB;
//如果pa == pb != NULL，就是找到交点，结束循环
//当pa ==pb == NULL，要么是两个一样长的链表，各自都走完了，但是没有交点；要么是pa和pb都将链表AB走了一遍while (pa != pb){if (pa == NULL) {pa = headB;} else {pa = pa->next;}if (pb == NULL) {pb = headA;} else {pb = pb->next;}}return pa;
}这篇关于链表OJ----相交链表找交点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
