源碼地址：GitHub-算法通關(guān)村

1.hash

/**
     * 方法1  通過hash輔助查找
     *
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode FindFirstCommonNodeByMap(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Map<ListNode, Integer> map = new HashMap<>();
        while (headA != null) {
            map.put(headA, null);
            headA = headA.next;
        }
        while (headB != null) {
            if (map.containsKey(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

2.集合

/**
     * 方法2  通過集合輔助查找
     *
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode FindFirstCommonNodeBySet(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Set<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

3.棧

/**
     * 方法3  通過棧來輔助查找
     *
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Stack<ListNode> stackA = new Stack<>();
        Stack<ListNode> stackB = new Stack<>();

        while (headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            stackB.push(headB);
            headB = headB.next;
        }

        ListNode pNode = null;
        while (stackA.size() > 0 && stackB.size() > 0) {
            if (stackA.peek() == stackB.peek()) {
                pNode = stackA.pop();
                stackB.pop();
            } else {
                break;
            }
        }
        return pNode;
    }

4.雙指針

/**
     * 方法4  通過雙指針來輔助查找
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode ptrA = headA;
        ListNode ptrB = headB;

        while (ptrA != ptrB) {
            ptrA = ptrA == null ? headB : ptrA.next;
            ptrB = ptrB == null ? headA : ptrB.next;
        }

        return ptrA;
    }

文章來源地址http://www.zghlxwxcb.cn/news/detail-603977.html

到了這里，關(guān)于算法通關(guān)村第一關(guān)---鏈表經(jīng)典問題之兩個鏈表的第一個公共節(jié)點筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！