1、判斷兩個鏈表是否相交，若相交，求交點。（假設鏈表不帶環）

兩個指針同時指向兩個鏈表，分別依次往后遍歷鏈表到最后一個節點，如指針的值相同（即節點地址相同），反之沒有交點。

int IsCross(Node* pHead1, Node* pHead2) {Node* Node1 = pHead1;Node* Node2 = pHead2;if((NULL == pHead1) || (NULL == pHead2)){return 0;}while(Node1->next){Node1 = Node1->next;}while(Node2->next){Node2 = Node2->next;}if(Node1 == Node2){return 1;}else{return 0;} }

求交點：先對兩個鏈表做對齊處理，然后同時遍歷，看節點地址是否相同，遇到第一個相同的節點即交點

Node* GetCrossNode(Node* pHead1, Node* pHead2) {Node* Node = pHead1;int steps = 0;int len1 = Size(pHead1);int len2 = Size(pHead2);int result = IsCross(pHead1, pHead2);if(result == 0 || (NULL == pHead1) || (NULL == pHead2) ){return NULL;}if(len1 > len2)steps = len1-len2;elsesteps = len2-len1;Node = ( len1 > len2 ? pHead1:pHead2 );while ( steps-- ) //對齊處理{Node = Node->next;}len1> len2 ?( pHead1 = Node) : (pHead2 = Node);while ( pHead1 != pHead2 ){pHead1 = pHead1->next, pHead2 = pHead2->next;}return pHead1; }

2、 判斷兩個鏈表是否相交，若相交，求交點。（假設鏈表可能帶環）
1）環外相交：

2）環內相交：

判斷是否相交：

int IsCrossWithCircle(Node* pHead1, Node* pHead2) {Node* fast = pHead1;Node* slow = pHead2;while( fast && slow && fast != slow ){slow = slow->next;if(fast->next){fast=fast->next->next;}else{fast = fast->next;}}if(fast && slow && fast == slow)return 1;elsereturn 0;}
求交點：對于環內相交，環上所有的點相同，無交點；環外相交，就相當于不考慮帶環的情況，參看上述方法

總結

以上是生活随笔為你收集整理的]数据结构：单链表之判断两个链表是否相交及求交点（带环、不带环）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。