查找两个链表第一个公共子节点

题目说明

输入两个链表,找出它们的第一个公共结点

在这里插入图片描述
两个链表的头结点都是已知的,相交之后成为一个单链表,但是相交位置未知,并且相交之前的结点数也是未知的,请设计算法找到两个链表的合并


(1)暴力求解

思路通过冒泡方式遍历两个链表,将第一个表中的每一个结点依次与第二个链表的每一个结点进行比较,当出现相同的结点指针,即为相交结点

注意:该方法虽然简单理解,但是如果要考虑时间复杂度,暴力求解法一般都是最慢的,耗时最高的

/**
 * 1.暴力求解循环遍历两个链表,判断结点相同
 * @param headA
 * @param headB
 * @return
 */
public static ListNode findFirstCommonNodeByViolence(ListNode headA, ListNode headB) {
    // 每一个结点进行比较判断是否相同
    ListNode A = headA;
    ListNode B = headB;
    while (A != null) {
        while (B != null) {
            if (A == B) {
                return A;
            }
            B = B.next;
        }
        B = headB;
        A = A.next;
    }
    return null;
}

(2)使用哈希Hash

思路:将第一个链表的元素全部存入到HashMap里面然后一边遍历第二个链表,一边检查当前元素是否在HashMap

提示:Java中的Map包含containsKey等方法可以检测该Map是否包含元素

在这里插入图片描述

 /**
  * 2.使用Hash方法
  * @param headA
  * @param headB
  * @return
  */
public static ListNode findFirstCommonNodeByMap(ListNode headA, ListNode headB) {
    Map&lt;ListNode, Integer&gt; hashMap = new HashMap<&gt;();

    while (headA != null) {
        hashMap.put(headA, null); // 链表中的所有结点存入HashMap中
        headA = headA.next;
    }

    while (headB != null) {
        if (hashMap.containsKey(headB)) { // 判断HashMap中是否包含headB,包含说明找到了公共结点,直接返回即可
            return headB;
        }
        headB = headB.next;
    }
    return null;
}

(3)使用集合⭐ – 与Hash类似

思路本质其实和哈希Hash没有太大区别,只是换了一个存储空间,将所有的结点存入到集合中,然后一边遍历,一边检查当前元素是否在HashSet中

问题为什么使用Set,而不使用其他集合,如List等等

解释:并不是说不可以使用List集合,相反可以使用List集合,也是可以的,但是List集合的运行时间和第一种暴力求解没有什么区别,这是由于List集合是有序的,每次存进去其实还会需要记录一个相当于sort排序的值,它第几个进来的,这个也是会占用内存,导致运行时间变长,而Set集合是无序的,不需要记录一个sort值,因此使用Set的速度就快,并且我们追进HashSet的源码进去查看,可以发现HashSet其实就是new HashMap对象,也就是HashSet就是HashMap,跟哈希Hash是没有本质区别

/**
 * 3.使用集合的方法
 * @param headA
 * @param headB
 * @return
 */
public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {
    Set<ListNode&gt; set = new HashSet<&gt;();
    // 循环遍历head1,将head1所有元素存到set
    while (headA != null) {
        set.add(headA);
        headA = headA.next;
    }

    // 循环遍历head2,判断set集合链表是否包含head2
    while (headB != null) {
        if (set.contains(headB)) {
            return headB;
        }
        headB = headB.next;
    }
    return null;
}

(4)使用栈⭐

思路:将两个链表分别存入到两个栈中,两边同时出栈判断是否一致,如果一致则说明存在相交,那么我们就继续查找,直到不一致,说明相同的结点都已经出栈了,就已经找到了两个链表的公共结点

提示:栈是后进先出,存进去后相同的都在后面,因此相同的结点也就是存在栈顶

/**
 * 4.通过栈的方法
 * @param headA
 * @param headB
 * @return
 */
public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {
    Stack<ListNode&gt; stackA = new Stack();
    Stack<ListNode&gt; 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 (stackB.size() > 0 &amp;&amp; stackA.size() > 0) {
        // 由于存是从头存到底部,因此后面的结点都是相同的,当取出来是不一样的时候说明从公共结点分隔出去了,到分岔口了,那就直接break即可
        if (stackA.peek() == stackB.peek()) { // peek表示查看此堆栈顶部对象,但是不会删除,而pop是直接返回了,也就删除
            preNode = stackA.pop();
            stackB.pop();
        } else {
            break;
        }
    }
    return preNode;
}

(5)仍有更多方法,作者尚未理解,理解会发出

原文地址:https://blog.csdn.net/weixin_65508929/article/details/134741044

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_26900.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注