算法通关村第一关——链表经典问题之两个链表第一个公共子节点笔记

落日映苍穹つ 2024-03-17 21:02 110阅读 0赞

#### 问题描述    ####

> 输入两个链表，找出它们的第一个公共子节点。如下图所示：

![8085ce8cffd2487cac88521f84997795.png][]

> 两个链表的头节点都是已知的，相交后形成一个新的单链表，但是相交的位置不知，并且相交前的节点数都是未知的，请你设计算法找到连个链表的合并点

#### 解题思路 ####

> 题目找两个单链表第一次相交的公共子节点，可以使用集合将单链表同时存储，通过contains方法就能找到元素相同的子节点，同时利用Hash也能很快实现（Set集合）；
> 
> 栈（先进后出）也可以实现，将两个单链表同时压入两个栈中，然后在将栈中元素进行出栈，与此同时进行元素的比较，如果出现两个元素相同，则说明两个单链表存在相交，最后找到最晚出栈的那一组元素即可。

#### 实现方法 ####

##### 集合实现 #####

> Set集合实现查找公共子节点代码如下

/**
         *  方法1 使用Set集合
         * @param headA A链表的头节点
         * @param headB B链表的头节点
         * @return 公共子节点
         */
        public ListNode findFirstCommonNodeBySet(ListNode headA , ListNode headB){
            Set<ListNode> listNodes = new HashSet<>();
            while (headA != null){
                listNodes.add(headA);
                headA = headA.next;
            }
    
            while (headB != null ){
                if (listNodes.contains(headB)){
                    return headB;
                }
                headB = headB.next;
            }
            return null;
        }

上述Set集合的实现过程是，先将A链表的节点元素通过while循环添加进set集合中，再遍历链表B,判断集合中是否有相交的元素，如果没有，继续遍历，直至遍历完整个B链表

##### 栈实现 #####

> 栈实现查找公共子节点代码如下

/**
         * 方法2 使用栈来实现
         * @param headA A链表头节点
         * @param headB B链表头节点
         * @return 公共子节点
         */
        public ListNode findFirstCommonNodeByStack(ListNode headA , ListNode headB){
            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 preNode = null;
            while (stackA.size() > 0 && stackB.size() >0){
                if (stackA.peek() == stackB.peek()){
                    preNode = stackA.pop();
                    stackB.pop();
                }else {
                    break;
                }
            }
            return preNode;
        }

上述栈实现的过程是先分别使用stackA和stackB两个栈存放A和B两个链表的节点元素，再在AB两个栈的长度范围内一个个比较将要出栈的元素是否相等，如果相等，则同时出栈

[8085ce8cffd2487cac88521f84997795.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/1b29092adacc4a0b877dbbc4b52c4694.png