題目鏈接： 力扣

題目描述

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

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

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

題目分析

兩鏈表是相交，不是交叉，因而只要找到相交的起始結(jié)點，之后的結(jié)點都認為是相交的。

如下圖所示，相交的起始結(jié)點認為是c1

代碼實現(xiàn)

解題思路1：哈希集合

用哈希集合存儲鏈表A節(jié)點，若集合中存在鏈表B的節(jié)點說明相交。

解題思路2：雙指針

兩鏈表都不為空時，創(chuàng)建兩個指針 pA和 pB，初始時分別指向兩個鏈表的頭節(jié)點 headA 和 headB，然后將兩個指針依次遍歷兩個鏈表的每個節(jié)點。

每步操作需要同時更新指針 pA 和 pB。

如果指針pA 不為空，則將指針移到下一個節(jié)點；如果指針 pB 不為空，則將指針移到下一個節(jié)點。

如果指針pA 為空，則將指針移到鏈表 headB 的頭節(jié)點；如果指針 pB 為空，則將指針移到鏈表headA 的頭節(jié)點。

當指針 pA 和 pB 指向同一個節(jié)點或者都為空時，返回它們指向的節(jié)點或者 null。

  /**
     * hash集合
     *
     * 時間復(fù)雜度：O(m+n)，m 和 n 分別指鏈表 headA 和 headB 的長度
     * 空間復(fù)雜度：O(m)
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<ListNode>();
        ListNode temp = headA;
        // headA放入集合
        while (temp != null){
            set.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null){
            if(set.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }


    /**
     * 雙指針
     *
     * 時間復(fù)雜度：O(m+n)，m 和 n 分別指鏈表 headA 和 headB 的長度
     * 空間復(fù)雜度：O(1)
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }