160. 相交鏈表

難度：簡單

題目

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

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

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

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

自定義評測：

評測系統(tǒng) 的輸入如下（你設計的程序 不適用 此輸入）：

• intersectVal - 相交的起始節(jié)點的值。如果不存在相交節(jié)點，這一值為 0
• listA - 第一個鏈表
• listB - 第二個鏈表
• skipA - 在 listA 中（從頭節(jié)點開始）跳到交叉節(jié)點的節(jié)點數(shù)
• skipB - 在 listB 中（從頭節(jié)點開始）跳到交叉節(jié)點的節(jié)點數(shù)

評測系統(tǒng)將根據(jù)這些輸入創(chuàng)建鏈式數(shù)據(jù)結(jié)構(gòu)，并將兩個頭節(jié)點 headA 和 headB 傳遞給你的程序。如果程序能夠正確返回相交節(jié)點，那么你的解決方案將被 視作正確答案 。

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點的值為 8 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,6,1,8,4,5]。
在 A 中，相交節(jié)點前有 2 個節(jié)點；在 B 中，相交節(jié)點前有 3 個節(jié)點。
— 請注意相交節(jié)點的值不為 1，因為在鏈表 A 和鏈表 B 之中值為 1 的節(jié)點 (A 中第二個節(jié)點和 B 中第三個節(jié)點) 是不同的節(jié)點。換句話說，它們在內(nèi)存中指向兩個不同的位置，而鏈表 A 和鏈表 B 中值為 8 的節(jié)點 (A 中第三個節(jié)點，B 中第四個節(jié)點) 在內(nèi)存中指向相同的位置。

示例 2：

輸入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節(jié)點的值為 2 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [1,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
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 沒有交點，intersectVal 為 0
• 如果 listA 和 listB 有交點，intersectVal == listA[skipA] == listB[skipB]

**進階：**你能否設計一個時間復雜度 O(m + n) 、僅用 O(1) 內(nèi)存的解決方案？

個人題解

也可考慮將一條鏈用 HashSet 存儲判斷

方法一：棧

用棧存儲一條鏈，通過棧從后往前遍歷棧同時每次都遍歷另一條鏈比對，直到不相等時返回。

時間復雜度O(m * n)

空間復雜度O(m)

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Deque<ListNode> stack = new LinkedList<>();ListNode ans = headA;while (ans != null) {stack.push(ans);ans = ans.next;}while (!stack.isEmpty()) {ListNode pop = stack.pop();ListNode other = headB;while (other != null) {if (other == pop) {break;}other = other.next;}if (other == null) {break;}ans = other;}return ans;}
}

參考題解

根據(jù)題目意思 如果兩個鏈表相交，那么相交點之后的長度是相同的

我們需要做的事情是，讓兩個鏈表從同距離末尾同等距離的位置開始遍歷。這個位置只能是較短鏈表的頭結(jié)點位置。 為此，我們必須消除兩個鏈表的長度差

1. 指針 pA 指向 A 鏈表，指針 pB 指向 B 鏈表，依次往后遍歷
2. 如果 pA 到了末尾，則 pA = headB 繼續(xù)遍歷
3. 如果 pB 到了末尾，則 pB = headA 繼續(xù)遍歷
4. 比較長的鏈表指針指向較短鏈表head時，長度差就消除了
5. 如此，只需要將最短鏈表遍歷兩次即可找到位置

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;
}

作者：房建斌學算法
鏈接：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/10774/tu-jie-xiang-jiao-lian-biao-by-user7208t/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。