外贸推广建站蓝颜seo牛,网站建设服务费如何做会计分录,郑州保洁公司,建公司的步骤文章目录 查找两个链表的第一个公共子节点#xff08;1#xff09;暴力求解法#xff08;2#xff09;使用哈希Hash⭐#xff08;3#xff09;使用集合⭐ - 与Hash类似#xff08;4#xff09;使用栈⭐#xff08;5#xff09;仍有更多方法#xff0c;作者尚未理解1暴力求解法2使用哈希Hash⭐3使用集合⭐ - 与Hash类似4使用栈⭐5仍有更多方法作者尚未理解理解会发出 查找两个链表的第一个公共子节点
原题Leetcode CR 171. 训练计划 V
题目说明 输入两个链表找出它们的第一个公共结点。 两个链表的头结点都是已知的相交之后成为一个单链表但是相交的位置未知并且相交之前的结点数也是未知的请设计算法找到两个链表的合并点 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) {MapListNode, Integer hashMap new HashMap();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) {SetListNode set new HashSet();// 循环遍历head1将head1所有元素存到set中while (headA ! null) {set.add(headA);headA headA.next;}// 循环遍历head2判断set集合链表是否包含head2while (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) {StackListNode stackA new Stack();StackListNode 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 stackA.size() 0) {// 由于存是从头存到底部因此后面的结点都是相同的当取出来是不一样的时候说明从公共结点分隔出去了到分岔口了那就直接break即可if (stackA.peek() stackB.peek()) { // peek表示查看此堆栈顶部的对象但是不会删除而pop是直接返回了也就删除了preNode stackA.pop();stackB.pop();} else {break;}}return preNode;
}5仍有更多方法作者尚未理解理解会发出
