原題鏈接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

目錄

1. 題目描述

2. 思路分析

3. 代碼實(shí)現(xiàn)

---

1. 題目描述

?

2. 思路分析

看到這道題，很容易想到的方法就是暴力求解，就是將一個(gè)鏈表的每個(gè)結(jié)點(diǎn)的地址分別和另外一個(gè)鏈表的每個(gè)結(jié)點(diǎn)的地址進(jìn)行比較，如果有相等的，就說明相交了。（注意這里不能比值，因?yàn)閮蓚€(gè)不同的結(jié)點(diǎn)值有可能一樣）。但是這樣的時(shí)間復(fù)雜度太高了，為O(N^2)。

這道題有一個(gè)很好的做法：

先計(jì)算出兩個(gè)鏈表的長度，讓長的鏈表先走相差的長度，然后兩個(gè)鏈表同時(shí)走，直到遇到相同的結(jié)點(diǎn)，即為第一個(gè)公共結(jié)點(diǎn)。

我們定義了四個(gè)變量curA，curB，lenA，lenB。

我們用結(jié)構(gòu)體指針curA遍歷鏈表A，用結(jié)構(gòu)體指針curB遍歷鏈表B。

lenA表示鏈表A的長度，lenB表示鏈表B的長度。

用while循環(huán)通過遍歷分別得到了鏈表A和B的長度。

我們判斷尾結(jié)點(diǎn)是否相等，如果尾結(jié)點(diǎn)相等，說明兩個(gè)鏈表一定相交！！！

（我們看下圖，如果兩個(gè)鏈表相交，那么從這個(gè)相交的結(jié)點(diǎn)（包括這個(gè)交點(diǎn)）之后的結(jié)點(diǎn)，在兩個(gè)鏈表中都是相等的。所以尾結(jié)點(diǎn)相等，說明兩個(gè)鏈表一定相交。）

如果兩個(gè)鏈表不相交（curA!=curB），我們直接返回空指針NULL。

如果兩個(gè)鏈表相交，我們先讓長的鏈表走兩個(gè)鏈表長度的差距步（gap）。因?yàn)椴恢纼蓚€(gè)鏈表哪個(gè)長，所以我們使用了abs()函數(shù)，差距步gap就是abs(lenA-lenB）。

之后我們又引入了兩個(gè)結(jié)構(gòu)體指針longList和shortList分別指向長鏈表和短鏈表的頭。這里用了if語句判斷，先假設(shè)某個(gè)鏈表是長鏈表，如果不是，就讓它等于短鏈表。

然后我們用一個(gè)while循環(huán)讓長鏈表走差距步（while(gap--)）。

然后讓longList和shortList這兩個(gè)結(jié)構(gòu)體指針同時(shí)走，找交點(diǎn)，找到交點(diǎn)時(shí)結(jié)束循環(huán)。

最后返回longList即可。

3. 代碼實(shí)現(xiàn)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curA=headA,*curB=headB;int lenA=1,lenB=1;//計(jì)算鏈表長度while(curA->next){curA=curA->next;  ++lenA;}while(curB->next){curB=curB->next;++lenB;}//不相交if(curA!=curB)return NULL;int gap=abs(lenA-lenB);struct ListNode *longList=headA,*shortList=headB;if(lenA<lenB){longList=headB;shortList=headA;}//長的先走差距步while(gap--){longList=longList->next;}//同時(shí)走找交點(diǎn)while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return longList;
}

?