一.前言

今天在力扣上刷到了一道題，想著和大家一起分享一下這道題——相交鏈表https://leetcode.cn/problems/intersection-of-two-linked-lists廢話不多說(shuō)，讓我們開(kāi)始今天的分享吧。

二.正文

1.1題目描述

是不是感覺(jué)好長(zhǎng)，我也這么覺(jué)得。哈哈，不過(guò)沒(méi)辦法，大家們湊合看一下吧，畢竟人家的題就那么長(zhǎng)。

1.2題目分析

我想到有兩種方法，一種是暴力求解，時(shí)間復(fù)雜度是O（N^2），還有一種是一種稍微巧妙一點(diǎn)的技巧，時(shí)間復(fù)雜度是(N)。

兩種方法共同部分：

我們可以創(chuàng)建兩個(gè)指針?lè)謩e是指向headA和headB的 ，pcur1和pcur2。并讓pcur1=headA

pcur2=pcurB。

我們首先需要判斷該鏈表是不是相交鏈表，如果是，則返回相交鏈表的第一個(gè)相交節(jié)點(diǎn)。否則，返回NULL。那么如何判斷該鏈表是不是相交鏈表呢？其實(shí)我們可以讓pcur1和pcur2分別遍歷兩個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)即可，如果pcur1=pcur2則說(shuō)明兩個(gè)鏈表至少有一個(gè)相交節(jié)點(diǎn)，毫無(wú)疑問(wèn)這肯定是相交節(jié)點(diǎn)。反之，pcur1！=pcur2，則說(shuō)明，不是相交鏈表。（值得注意的是，完成上面部分后，記得讓pcur1=headA，pcur2=headB，因?yàn)閜cur1和pcur2后續(xù)我們還需要重新遍歷兩個(gè)鏈表）

（i）暴力算法：

我們可以讓headA中的每一個(gè)節(jié)點(diǎn)都與headB中的節(jié)點(diǎn)遍歷一次，然后讓headA的下一個(gè)節(jié)點(diǎn)，重復(fù)這個(gè)動(dòng)作，直到headA的最后一個(gè)節(jié)點(diǎn)遍歷結(jié)束。

這是該方法的代碼：

/*** 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)非暴力算法：

那么我們應(yīng)該依據(jù)什么來(lái)遍歷相對(duì)長(zhǎng)度前的數(shù)據(jù)呢？我們可以利用在遍歷A和B的同時(shí)，讓代表A鏈表len1++來(lái)算出長(zhǎng)度，同理len2是算出B的長(zhǎng)度。定義一個(gè)變量gap=abs（len1-len2）算出絕對(duì)值，如果A鏈表長(zhǎng)，則A鏈表先遍歷gap個(gè)長(zhǎng)度的節(jié)點(diǎn)，反之B鏈表長(zhǎng)則，B鏈表先遍歷gap個(gè)長(zhǎng)度的節(jié)點(diǎn)。

最后的步驟是上圖所示，相對(duì)長(zhǎng)度中的上下節(jié)點(diǎn)依次比較。

三.結(jié)言

今天的題目分享就到此結(jié)束了，拜拜了，家人們。