链表--1.判断两个链表是否相交，若相交，求交点。（假设链表不带环）2.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）

本文主要是介绍链表--1.判断两个链表是否相交，若相交，求交点。（假设链表不带环）2.判断两个链表是否相交，若相交，求交点。（假设链表可能带环），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.判断两个链表是否相交，若相交，求交点。（假设链表不带环）

1.若链表不带环
则若相交只有一种方式。
这里写图片描述
方法一：
把List2链接到List1的后面，再遍历List2，如果List2有环则说明相交。且List2的头一定在环上。

方法二：
将List1与List2同时走到链表结尾,如果尾结点相同，则一定有环。
判断相交点：两个链表不一定一样长，所以先算出List1与List2的长度。然后求出两长度差len，将长的先走len步，再同时走，当他俩相遇的时候就为交点。

int Check_NoCricle(ListNode* pHead1,ListNode* pHead2)
{if(pHead1 == NULL || pHead2 == NULL)return -1;while(pHead1->Next)pHead1 = pHead1->Next;while(pHead2->Next)pHead2 = pHead2->Next;if(pHead1 == pHead2)return 1;return 0;
}ListNode* GetList_EnterNode(ListNode* pHead1,ListNode* pHead2)
{assert(pHead1 && pHead2)int len1 = 0;int len2 = 0;ListNode* pCur1 = pHead1;ListNode* pCur2 = pHead2;while(pCur1){len1++;pCur1 = pCur1->Next;}while(pCur2){len2++;pCur2 = pCur2->Next;}pCur1 = pHead1;pCur2 = pHead2;int lensub = len1-len2;if(lensub <= 0){//List2长lensub = -lensub;while(lensub){pCur2 = pCur2->Next;lensub--;}}else{//List1长while(lensub){pCur1 = pCur1->Next;lensub--;}}//走到这里两个链表长度是一样的while(pCur1 != pCur2){pCur1 = pCur1->Next;pCur2 = pCur2->Next;}return pCur1;
}

1.判断两个链表是否相交，若相交，求交点。（假设链表带环）

这里只给出思路。
若两链表可能带环
则
1.一个链表带环，一个链表不带环。这种情况不可能相交。
2.两个链表都带环。三种情况。这里只给出相交的两种情况。
这里写图片描述
如果交点在环外，则只有一个交点。

如果交点在环内，则有两个交点任意输出一个即可。
则先判断两个带环链表是否相交

ListNode* Find_CricleNode(ListNode* pHead1,ListNode* pHead2)
{assert(pHead1 && pHead2);ListNode* pCur1 = IsHaveCircle(pHead1);ListNode* pCur2 = IsHaveCircle(pHead2);//只要一个没有环，则不存在交点if(pCur1 == NULL  pCur2 == NULL)return GetList_EnterNode (pCur1,pCur2);//走到这里说明两个都有环ListNode* pMeet1 = FindLoopStart(pHead1);ListNode* pMeet2 = FindLoopStart(pHead2);if(pMeet1!=NULL && pMeet2!=NULL){ListNode* pTemp = pMeet1;while(pMeet1 != pTemp->Next){//这里一定要先判断第一个，并且这里输出的交点不一定一定是第一个交点。如果交点在环外则不是。if(pTemp == pMeet2)return pTenp;pTemp = pTemp->Next;}}    return NULL;
}