极客教程C++程序 查找两个链表交点
系统中有两个单链表。由于某个程序错误，其中一个链表的尾节点与第二个链表连接在一起，形成一个倒Y形的链表。编写程序获取两个链表合并的点。
上图显示一个具有交点为15的两个链表的示例。
方法一(简单地使用两个循环)：
使用2个嵌套的for循环。外部循环将为第一个列表的每个节点，内部循环将为第二个列表。在内部循环中，检查第二个列表中的任何节点是否与第一个链表的当前节点相同。这种方法的时间复杂度将为O（M * N），其中m和n是两个列表中的节点数。
方法二(标记已访问的节点)：
此解决方案需要修改基本的链表数据结构。每个节点都有一个visited标志。遍历第一个链表并保持标记已访问的节点。现在遍历第二个链表，如果再次看到已访问的节点，则存在交点，请返回交点节点。此解决方案在O(m + n)中工作，但需要每个节点的额外信息。可以使用哈希实现不需要修改基本数据结构的此解决方案变体。遍历第一个链表并在哈希中存储已访问节点的地址。现在遍历第二个链表，如果看到哈希中已经存在的地址，则返回交点节点。
方法三(使用节点计数的差异)：
- 获取第一个列表中节点的数量，将其计数为c1。
- 获取第二个列表中节点的数量，将其计数为c2。
- 获取计数之差 d = abs(c1 – c2)
- 现在从第一个节点开始遍历更大的列表，直到d个节点，以便从这里开始两个列表具有相等的节点数
- 然后我们可以同时遍历两个列表，直到遇到公共节点。 （请注意，获取公共节点是通过比较节点的地址完成的）
下图是上述方法的运行过程：
下面是上述方法的实现：
// C++程序获取两个链表的交点
#include
using namespace std;
//链接链表节点
class Node
{
public:
int data;
Node* next;
};
//获取链表中节点的数量函数
int getCount(Node* head);
/*获取head1和head2两个链表的交点的函数，其中head1比head2多d个节点*/
int _getIntesectionNode(int d, Node* head1,
Node* head2);
/*获取两个链表head1和head2的交点函数*/
int getIntesectionNode(Node* head1,
Node* head2)
{
//计算两个链表中节点的数量
int c1 = getCount(head1);
int c2 = getCount(head2);
int d;
//如果head1的数量大于head2的，交换它们
if (c1 > c2)
{
d = c1 - c2;
return _getIntesectionNode(d, head1,
head2);
}
else
{
d = c2 - c1;
return _getIntesectionNode(d, head2,
head1);
}
}
/*获取head1和head2两个链表的交点函数，其中head1比head2多d个节点*/
int _getIntesectionNode(int d, Node* head1,
Node* head2)
{
//在大链表的开头处
Node* current1 = head1;
Node* current2 = head2;
//遍历大链表，直到到达与小链表的相对位置
for (int i = 0; i < d; i++)
{
if (current1 == NULL)
{
return -1;
}
current1 = current1->next;
}
//同时向前移动两个链表的指针，直到它们相遇
while (current1 != NULL &&
current2 != NULL)
{
if (current1 == current2)
return current1->data;
//向前移动两个指针
current1 = current1->next;
current2 = current2->next;
}
return -1;
}
/*获取链表中节点的数量函数*/
int getCount(Node* head)
{
Node* current = head;
//计数器来存储节点的数量
int count = 0;
//遍历链表直到结束
while (current != NULL)
{
//增加计数器
count++;
//移动节点
current = current->next;
}
return count;
}
//主函数
int main()
{
/* 创建两个链表
第一个链表 3->6->9->15->30
第二个链表 10->15->30
15是交点*/
Node* newNode;
//添加新节点
Node* head1 = new Node();
head1->data = 10;
Node* head2 = new Node();
head2->data = 3;
newNode = new Node();
newNode->data = 6;
head2->next = newNode;
newNode = new Node();
newNode->data = 9;
head2->next->next = newNode;
newNode = new Node();
newNode->data = 15;
head1->next = newNode;
head2->next->next->next = newNode;
newNode = new Node();
newNode->data = 30;
head1->next->next = newNode;
head1->next->next->next = NULL;
cout << "交点为 " <<
getIntesectionNode(head1, head2);
}
//此代码由rathbhupendra提供```
输出:
交点为 15
时间复杂度: O(m+n)
辅助空间: O(1)
方法4(在第一个列表中创建圆圈):
感谢 Saravanan Man 提供以下解决方案。
1. 遍历第一个链接列表(计算元素的数量)，并创建一个循环链接列表。(记住最后一个节点，以便以后可以打破循环)。
2. 现在将问题视为查找第二个链接列表中的循环。 因此，问题得到解决。
3. 由于我们已经知道循环的长度(第一个链接列表的大小)，所以我们可以在第二个列表中遍历这些数字，然后从第二个列表的开头开始另一个指针。 我们必须遍历直到它们相等，这就是所需的交点。
4. 从链表中删除圆圈。
时间复杂度: O(m+n)
辅助空间: O(1)
方法5(反转第一个列表并创建方程):
1) 让X为第一个交点到交点的链表长度。
让Y为第二个交点到交点的链表长度。
让Z为包括交点节点在内的链接列表的从交点到末尾的长度。
我们有
X + Z = C1;
Y + Z = C2;
2) 反转第一个链接列表。
3) 遍历第二个链接列表。 让C3为第二个列表的长度-1。
现在我们有
X + Y = C3
我们有3个线性方程。 通过解决它们，我们得到
X = (C1 + C3 – C2)/2;
Y = (C2 + C3 – C1)/2;
Z = (C1 + C2 – C3)/2;
我们找到了交点。
4) 反转回第一个链接列表。
优点: 不需要比较指针。
缺点: 修改链接列表(反转列表)。
时间复杂度: O(m+n)
辅助空间: O(1)
方法6(遍历两个列表并比较最后节点地址): 此方法仅用于检测是否存在交点。(感谢NeoTheSaviour提出这个想法)
1) 遍历第1个列表，存储最后节点地址
2) 遍历第2个列表，存储最后节点地址。
3) 如果存储在1和2中的节点相同，则它们相交。
此方法的时间复杂度为O(m+n)，使用的辅助空间为O(1)
方法7(双指针技术):
使用两个指针：
- 将ptr1和ptr2初始化为head1和head2。
- 逐个节点遍历列表。
- 当ptr1到达列表的末端时，将其重定向到head2。
- 类似地，当ptr2到达列表的末端时，将其重定向到head1。
- 一旦它们都通过重新分配，它们将与碰撞点等距离。
- 如果在任何节点上ptr1遇到ptr2，则它是交点。
- 第二次迭代如果没有交点则返回NULL。
// C++程序来打印列表的交集
#include <bits/stdc++.h>
using namespace std;
//链表节点
class Node
{
public:
int data;
Node* next;
};
//返回交点的函数
Node* intersectPoint(Node* head1,
Node* head2)
{
// 在A和B的头部保持两个指针ptr1和ptr2，
Node* ptr1 = head1;
Node* ptr2 = head2;
// 如果任何一个头为空即没有交点
if (ptr1 == NULL || ptr2 == NULL)
{
return NULL;
}
// 遍历列表直到它们到达交点
while (ptr1 != ptr2) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
// 如果在任何节点ptr1遇到ptr2，那么它就是交点。返回交点即可。
if (ptr1 == ptr2)
{
return ptr1;
}
//一旦它们都通过重新分配，它们将从碰撞点等距离。
//当ptr1到达列表结尾时，重新分配为head2。
if (ptr1 == NULL)
{
ptr1 = head2;
}
//当ptr2到达列表结尾时，重定向为head1。
if (ptr2 == NULL)
{
ptr2 = head1;
}
}
return ptr1;
}
//在给定的链接列表中打印交点节点的函数
void print(Node* node)
{
if (node == NULL)
cout << "NULL";
while (node->next != NULL)
{
cout << node->data << "->";
node = node->next;
}
cout << node->data;
}
//主函数
int main()
{
/*创建两个链接列表
第一条链接列表是3->6->9->15->30
第二条链接列表是10->15->30
15 30是交点列表元素*/
Node* newNode;
Node* head1 = new Node();
head1->data = 10;
Node* head2 = new Node();
head2->data = 3;
newNode = new Node();
newNode->data = 6;
head2->next = newNode;
newNode = new Node();
newNode->data = 9;
head2->next->next = newNode;
newNode = new Node();
newNode->data = 15;
head1->next = newNode;
head2->next->next->next = newNode;
newNode = new Node();
newNode->data = 30;
head1->next->next = newNode;
head1->next->next->next = NULL;
Node* intersect_node = NULL;
//查找两个链接列表的交点节点
intersect_node = intersectPoint(head1,
head2);
cout << "INTERSEPOINT LIST :";
print(intersect_node);
return 0;
//此代码由bolliranadheer提供
}
输出：
INTERSEPOINT LIST :15->30
时间复杂度： O( m + n)
辅助空间： O(1)