題目描述

給你兩個單鏈表的頭節(jié)點?headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表沒有交點，返回 null 。

圖示兩個鏈表在節(jié)點 c1 開始相交：

題目數(shù)據(jù) 保證 整個鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。

注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

輸出：Intersected at '8'

解釋：相交節(jié)點的值為 8 （注意，如果兩個鏈表相交則不能為 0）。

從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。

在 A 中，相交節(jié)點前有 2 個節(jié)點；在 B 中，相交節(jié)點前有 3 個節(jié)點。

示例?2：

輸入：intersectVal?= 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

輸出：Intersected at '2'

解釋：相交節(jié)點的值為 2 （注意，如果兩個鏈表相交則不能為 0）。

從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。

在 A 中，相交節(jié)點前有 3 個節(jié)點；在 B 中，相交節(jié)點前有 1 個節(jié)點。

示例?3：

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

輸出：null

解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。

由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。

這兩個鏈表不相交，因此返回 null 。

?

提示：

listA 中節(jié)點數(shù)目為 m

listB 中節(jié)點數(shù)目為 n

0 <= m, n <= 3 * 104

1 <= Node.val <= 105

0 <= skipA <= m

0 <= skipB <= n

如果 listA 和 listB 沒有交點，intersectVal 為 0

如果 listA 和 listB 有交點，intersectVal == listA[skipA + 1] == listB[skipB + 1]

來源：力扣（LeetCode）

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

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

基本思路

遍歷鏈表 headA，將每個節(jié)點的引用存儲在哈希表中。然后遍歷鏈表 headB，檢查哈希表中是否存在相同的節(jié)點引用，如果存在則說明鏈表相交，返回相交節(jié)點；如果遍歷完鏈表 headB 都沒有找到相交節(jié)點，則返回 null。

時間復(fù)雜度分析：設(shè)鏈表 headA 的長度為 m，鏈表 headB 的長度為 n，遍歷鏈表 headA 和 headB 各需要 O(m+n) 的時間，因此總時間復(fù)雜度為 O(m+n)。

解法代碼（Go）

func getIntersectionNode(headA, headB *ListNode) *ListNode {
? ?nodeSet := make(map[*ListNode]bool)
? ?cur := headA
for cur != nil {
? ? ? ?nodeSet[cur] = true
? ? ? ?cur = cur.Next
}
? ?cur = headB
for cur != nil {
if _, ok := nodeSet[cur]; ok {
return cur
}
? ? ? ?cur = cur.Next
}
return nil
}



逐步驗算

實際應(yīng)用

這個函數(shù)的實際應(yīng)用是在兩個鏈表中找到它們的相交節(jié)點。通過比較每個鏈表中的節(jié)點是否在另一個鏈表中存在，可以確定它們的相交節(jié)點。

具體的應(yīng)用場景可以是：

1.? 鏈表相交檢測：可以用于判斷兩個鏈表是否相交。如果相交，可以返回相交的節(jié)點，否則返回空指針。這在解決鏈表相關(guān)的問題時非常有用，比如判斷兩個鏈表是否有公共部分。

2.? 鏈表環(huán)檢測：如果鏈表中存在環(huán)，可以使用這個函數(shù)來找到環(huán)的入口節(jié)點。具體方法是，將第一個鏈表中的節(jié)點添加到集合中，然后遍歷第二個鏈表，如果遇到一個節(jié)點在集合中已經(jīng)存在，則說明這個節(jié)點就是環(huán)的入口節(jié)點。

總結(jié)來說，這個函數(shù)可以用于鏈表相交檢測和鏈表環(huán)檢測的場景，幫助解決一些與鏈表相關(guān)的問題。