一共有四种方法:
- 哈希和集合
- 栈
- 拼接两个字符串
- 同步相消
1、哈希和集合法:
将一个链表存入Map(或者集合)中,然后遍历第二个链表,在遍历的同时,检查在Hash(或者集合)中是否包含此节点。
//哈希法
public static ListNode findFirstCommonNodeByMap(ListNode pHead1, ListNode pHead2) {
//判断两个链表的头结点是否为空,有一个为空,则无法寻找第一个公共节点
if (pHead1 == null || pHead2 == null) {
return null;
}
ListNode current1 = pHead1;
ListNode current2 = pHead2;
//创建一个Hash对象,用来存储链表元素
HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
while (current1 != null) {
hashMap.put(current1, null);
current1 = current1.next;
}
//遍历第二个链表,遍历的同时,检测Hash中是否包含此结点
while (current2 != null) {
if (hashMap.containsKey(current2))
return current2;
current2 = current2.next;
}
return null;
}
//集合法、与哈希法思想相似
public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {
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;
}
2、栈方法:
主要思想:栈是后进先出原则,stack.peek()方法每次比较栈顶元素,也就是链表最后一位,由于求第一个公共元素,那么,对于这两个链表来说,第一个公共结点到两个链表的最后一个结点距离是一致的,且值一一对应相等(举例:a链表,1->2->3->4->5,b链表,11->22->4->5。这俩链表第一个刚刚结点“4”,距离最后一位元素距离都是1,且a的4与b的4对应,a的5与b的5对应)。若第一次判断栈顶元素就不相等,那么这俩链表一定没有公共结点。
操作步骤:将两个链表分别压入两个栈中,先定义一个空的preNode对象,目的是:最终用来返回第一个公共子节点。先判断两个栈的大小都大于0,确保有值进行比较,然后依次获取两个栈的栈顶元素(stackA.peek() == stackB.peek()),如果相等将此栈顶元素弹栈,并且用preNode结点接受,然后继续比较两个栈顶元素是否相等,直到不等情况出现,那么此时preNode结点就是我们要寻找的第一个公共结点。
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) {
//比较栈顶元素是否相等
if (stackA.peek() == stackB.peek()) {
//若相等,将栈顶元素弹栈,并且用preNode结点接收
preNode = stackA.pop();
stackB.pop(); //第二个链表的栈,栈顶元素同样弹栈
} else {
break; //当判断两个栈顶元素首次不相等时,说明上一次弹栈的元素就是第一个公共结点
}
}
return preNode;
}
3、拼接字符串
主要思想:两个链表第一个公共结点起,到最后一个结点的值都相互对应。不放将两个链表以第一个公共结点为分界点彼此分为两部分,a链表的右半部分跟b链表的右半部分是一模一样的,所以不论是a接到b的后边,还是b接到a的后边,这两个字符串的最后一段一定是一模一样的。
示例图:
public static ListNode findFirstCommonNodeByCombine(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
if (p1 != p2) {//当p1==p2时,就意味着遍历到了 示例图 中的第四部分(公共元素部分)
//a链表遍历完后,将b链表拼接在a链表的后边
if (p1 == null) {
p1 = pHead2;
}
//同理,b链表遍历完后,将a链表
if (p2 == null) {
p2 = pHead1;
}
}
}
return p1;
}
4、同步相消
名词解释:同步相消就是,链表长的先消除几步,使得两个链表长度相等。然后两个链表同步遍历,结点第一次一致的时候,就是第一个公共结点。
文章来源:https://www.toymoban.com/news/detail-660456.html
public static ListNode findFirstCommonNodeBySub(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
ListNode current1 = pHead1;
ListNode current2 = pHead2;
int l1 = 0, l2 = 0;
//遍历链表得到链表的长度
while (current1 != null) {
current1 = current1.next;
l1++;
}
while (current2 != null) {
current2 = current2.next;
l2++;
}
//重新将两个指针分别指向链表的头结点
current1 = pHead1;
current2 = pHead2;
int sub = l1 > l2 ? l1 - l2 : l2 - l1;
if (l1 > l2) {
int a = 0;
while (a < sub) {
current1 = current1.next;
a++;
}
}
if (l1 < l2) {
int a = 0;
while (a < sub) {
current2 = current2.next;
a++;
}
}
//消除步差之后,同步遍历,然后看结点是否一致。首次一致,那么这个结点就是第一个公共结点
while (current2 != current1) {
current2 = current2.next;
current1 = current1.next;
}
return current1;
}
附录
完成上述操作所需的初始化代码(例如链表的构造及初始化、switch语句,方便使用不同的方法来实现)文章来源地址https://www.toymoban.com/news/detail-660456.html
public class FindFirstCommonNode {
public static void main(String[] args) {
ListNode[] heads = initLinkedList();
//la 为 1 2 3 4 5
//lb 为 11 22 4 5
ListNode la = heads[0];
ListNode lb = heads[1];
int testMethod = 5;
ListNode node = new ListNode(0);
switch (testMethod) {
case 1: //方法1:通过Hash辅助查找
node = findFirstCommonNodeByMap(la, lb);
break;
case 2: //方法2:通过集合辅助查找
node = findFirstCommonNodeBySet(la, lb);
break;
case 3://方法3:通过栈辅助查找
node = findFirstCommonNodeByStack(la, lb);
break;
case 4://方法4:通过拼接辅助查找
node = findFirstCommonNodeByCombine(la, lb);
break;
case 5://方法5:通过差辅助查找
node = findFirstCommonNodeBySub(la, lb);
break;
}
System.out.println("公共结点为:" + node.val);
}
private static ListNode[] initLinkedList() {
ListNode[] heads = new ListNode[2];
// 构造第一个链表交点之前的元素 1 ->2-> 3
heads[0] = new ListNode(1);
ListNode current1 = heads[0];
current1.next = new ListNode(2);
current1 = current1.next;
current1.next = new ListNode(3);
current1 = current1.next;
// 11->22
// 构造第二个链表交点之前的元素
heads[1] = new ListNode(11);
ListNode current2 = heads[1];
current2.next = new ListNode(22);
current2 = current2.next;
// 构造公共交点以及之后的元素
ListNode node4 = new ListNode(4);
current1.next = node4;
current2.next = node4;
ListNode node5 = new ListNode(5);
node4.next = node5;
ListNode node6 = new ListNode(6);
node5.next = node6;
return heads;
}
static class ListNode {
public int val;
public ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
}
到了这里,关于算法通关村第一关------链表经典问题之寻找第一个公共子结点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!