leetcode算法160.相交連結清單

哈喽！大家好，我是【學無止境小奇】，一位熱愛分享各種技術的部落客！

⭐【學無止境小奇】的創作宗旨：每一條指令都親自執行過，每一行代碼都實際運作過，每一種方法都真實實踐過，每一篇文章都良心制作過。✊✊✊

⭐【學無止境小奇】的部落格中所有涉及指令、代碼的地方，除了提供圖檔供大家參考，另外會在圖檔下方提供一份純文字格式的指令或者代碼友善大家粘貼複制直接執行指令或者運作代碼。

⭐如果你對技術有着濃厚的興趣，歡迎關注【學無止境小奇】，歡迎大家和我一起交流。

❤️❤️❤️感謝各位朋友接下來的閱讀❤️❤️❤️

文章目錄

• ​​一、leetcode算法​​

• ​​ 1、相交連結清單​​

• ​​1.1、題目​​
• ​​1.2、思路​​
• ​​1.3、答案​​

一、leetcode算法

1、相交連結清單

1.1、題目

給你兩個單連結清單的頭節點 headA 和 headB ，請你找出并傳回兩個單連結清單相交的起始節點。如果兩個連結清單不存在相交節點，傳回 null 。

圖示兩個連結清單在節點 c1 開始相交：

題目資料 保證 整個鍊式結構中不存在環。

注意，函數傳回結果後，連結清單必須 保持其原始結構 。

自定義評測：

評測系統 的輸入如下（你設計的程式 不适用 此輸入）：

intersectVal - 相交的起始節點的值。如果不存在相交節點，這一值為 0

listA - 第一個連結清單

listB - 第二個連結清單

skipA - 在 listA 中（從頭節點開始）跳到交叉節點的節點數

skipB - 在 listB 中（從頭節點開始）跳到交叉節點的節點數

評測系統将根據這些輸入建立鍊式資料結構，并将兩個頭節點 headA 和 headB 傳遞給你的程式。如果程式能夠正确傳回相交節點，那麼你的解決方案将被 視作正确答案 。

示例 1：

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

輸出：Intersected at ‘8’

解釋：相交節點的值為 8 （注意，如果兩個連結清單相交則不能為 0）。

從各自的表頭開始算起，連結清單 A 為 [4,1,8,4,5]，連結清單 B 為 [5,6,1,8,4,5]。

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

示例 2：

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

輸出：Intersected at ‘2’

解釋：相交節點的值為 2 （注意，如果兩個連結清單相交則不能為 0）。

從各自的表頭開始算起，連結清單 A 為 [1,9,1,2,4]，連結清單 B 為 [3,2,4]。

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

示例 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 。

1.2、思路

思路一：此題我們可以先把A連結清單放入哈希表中，然後再将B連結清單放入哈希表中，如果有重複的值就直接傳回會相交的值。

1.3、答案

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while(temp != null){
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while(temp != null){
            if(visited.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}      

複雜度分析

時間複雜度：O(m+n)，其中 m 和 n 是分别是連結清單headA 和 headB 的長度。需要周遊兩個連結清單各一次。