一.前言
今天在力扣上刷到了一道題，想著和大家一起分享一下這道題——相交鏈表https://leetcode.cn/problems/intersection-of-two-linked-lists廢話不多說，讓我們開始今天的分享吧。
二.正文
1.1題目描述
是不是感覺好長，我也這么覺得。哈哈，不過沒辦法，大家們湊合看一下吧，畢竟人家的題就那么長。
1.2題目分析
我想到有兩種方法，一種是暴力求解，時間復雜度是O（N^2），還有一種是一種稍微巧妙一點的技巧，時間復雜度是(N)。
兩種方法共同部分：
我們可以創建兩個指針分別是指向headA和headB的 ，pcur1和pcur2。并讓pcur1=headA
pcur2=pcurB。
我們首先需要判斷該鏈表是不是相交鏈表，如果是，則返回相交鏈表的第一個相交節點。否則，返回NULL。那么如何判斷該鏈表是不是相交鏈表呢？其實我們可以讓pcur1和pcur2分別遍歷兩個鏈表的最后一個節點即可，如果pcur1=pcur2則說明兩個鏈表至少有一個相交節點，毫無疑問這肯定是相交節點。反之，pcur1！=pcur2，則說明，不是相交鏈表。（值得注意的是，完成上面部分后，記得讓pcur1=headA，pcur2=headB，因為pcur1和pcur2后續我們還需要重新遍歷兩個鏈表）
（i）暴力算法：
我們可以讓headA中的每一個節點都與headB中的節點遍歷一次，然后讓headA的下一個節點，重復這個動作，直到headA的最后一個節點遍歷結束。
這是該方法的代碼：
/*** Definition for singly-linked list.* struct ListNode {* ? ? int val;* ? ? struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
ListNode* pcur1,*pcur2;
pcur1=headA;
pcur2=headB;
while(pcur1->next!=NULL)
{pcur1=pcur1->next;
}
while(pcur2->next!=NULL)
{pcur2=pcur2->next;
}
if(pcur2!=pcur1)
return NULL;
pcur1=headA;
pcur2=headB;
while(pcur1->next!=NULL)
{
while(pcur2->next!=NULL)
{
if(pcur1==pcur2)
return pcur1;
pcur2=pcur2->next;
}
pcur2=headB;
pcur1=pcur1->next;
}
return pcur1;
}(ii)非暴力算法：
那么我們應該依據什么來遍歷相對長度前的數據呢？我們可以利用在遍歷A和B的同時，讓代表A鏈表len1++來算出長度，同理len2是算出B的長度。定義一個變量gap=abs（len1-len2）算出絕對值，如果A鏈表長，則A鏈表先遍歷gap個長度的節點，反之B鏈表長則，B鏈表先遍歷gap個長度的節點。
最后的步驟是上圖所示，相對長度中的上下節點依次比較。
三.結言
今天的題目分享就到此結束了，拜拜了，家人們。
