查找两个链表的第一个公共子节点
两个链表的头结点都是已知的,相交之后成为一个单链表,但是相交的位置未知,并且相交之前的结点数也是未知的,请设计算法找到两个链表的合并点
(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⭐
/**
* 2.使用Hash的方法
* @param headA
* @param headB
* @return
*/
public static ListNode findFirstCommonNodeByMap(ListNode headA, ListNode headB) {
Map<ListNode, 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中
解释:并不是说不可以使用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> set = new HashSet<>();
// 循环遍历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> 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 (stackB.size() > 0 && 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进行投诉反馈,一经查实,立即删除!