算法通关村第一关---链表经典问题之两个链表的第一个公共节点笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村第一关---链表经典问题之两个链表的第一个公共节点笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

源码地址：GitHub-算法通关村

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;
    }

文章来源地址https://www.toymoban.com/news/detail-603977.html

到了这里，关于算法通关村第一关---链表经典问题之两个链表的第一个公共节点笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！