爪哇2博客
爪哇2博客

两个链表的交集

在这篇文章中,我们将看到如何找到两个链表的交集。


问题

给两个 单链表,查找两个链接列表是否相交。如果它们相交,请找到相交点。


这是找到两个链表的交集的简单算法。

  • 查找两个单链列表的长度。
  • 找到更大的链表,然后迭代两个链表之间的差异。
  • 请注意,在此步骤中,两个链表将变得相等。
  • 遍历两个链表,并检查是否有任何公共节点,如果找到一个,则将其返回。
  • 否则返回null。

链表.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
组织.Arpit.爪哇2blog;
 
上市 链表{
 
私人的 节点 ;
 
私人的 静态的 节点 {
私人的 整型 ;
私人的 节点 下一页;
 
节点(整型 ) {
这个. = ;
 
}
}
 
上市 虚空 addToTheLast(节点 节点) {
 
如果 ( == 空值) {
= 节点;
} 其他 {
节点 温度 = ;
(温度.下一页 != 空值)
温度 = 温度.下一页;
 
温度.下一页 = 节点;
}
}
 
 
上市 节点 findIntersectionNode(节点 list1, 节点 list2) {
整型 lengthOfList1 = 0;
整型 lengthOfList2 = 0;
节点 温度1=list1, 温度2=list2;
如果 (温度1 == 空值 || 温度2 == 空值)
返回 空值;
 
//查找两个链表的长度
(温度1 != 空值){
lengthOfList1++;
温度1 = 温度1.下一页;
}
(温度2 != 空值){
lengthOfList2++;
温度2 = 温度2.下一页;
}
 
整型 区别 = 0;
节点 ptr1=list1;
节点 ptr2=list2;
 
//查找更大的链表,并迭代到两个链表之间的差异。
如果(lengthOfList1 > lengthOfList2){
区别 = lengthOfList1-lengthOfList2;
整型 i=0;
(i<区别){
ptr1 = ptr1.下一页;
i++;
}
}其他{
区别 = lengthOfList2-lengthOfList1;
整型 i=0;
(i<区别){
ptr2 = ptr2.下一页;
i++;
}
}
 
//遍历两个链表并找到公共节点
(ptr1 != 空值 && ptr2 != 空值){
如果(ptr1 == ptr2){
返回 ptr1;
}
ptr1 = ptr1.下一页;
ptr2 = ptr2.下一页;
}
 
返回 空值;
}
 
上市 静态的 虚空 主要([] args) {
链表 list1 = 链表();
//创建链接列表
节点 头1= 节点(5);
list1.addToTheLast(头1);
list1.addToTheLast( 节点(6));
节点 节点 = 节点(7);
list1.addToTheLast(节点);
list1.addToTheLast( 节点(1));
list1.addToTheLast( 节点(2));
 
链表 list2 = 链表();
节点 头2= 节点(4);
list2.addToTheLast(头2);
list2.addToTheLast(节点);
 
节点 findIntersectionNode = list1.findIntersectionNode(头1, 头2);
如果(findIntersectionNode==空值)
{
系统..打印(“两个链接列表不相交!”);
}
其他
{
系统..打印(“相交节点:”+findIntersectionNode.);
}
}
 
}
 

当您在程序上方运行时,将获得以下输出

相交节点:7

那就是找到两个链表的交集。


导入联系人

您可能还喜欢:

分享这个

作者

关注作者

相关文章

发表评论

您的电子邮件地址不会被公开。 必需的地方已做标记 *

订阅我们的新闻

获取质量教程到您的收件箱。现在订阅。


成为朋友

©2020 爪哇2博客