C++程序查找两个链表交点

系统中有两个单链表。由于某个程序错误，其中一个链表的尾节点与第二个链表连接在一起，形成一个倒Y形的链表。编写程序获取两个链表合并的点。

C++程序查找两个链表交点

上图显示一个具有交点为15的两个链表的示例。

方法一(简单地使用两个循环)：

使用2个嵌套的for循环。外部循环将为第一个列表的每个节点，内部循环将为第二个列表。在内部循环中，检查第二个列表中的任何节点是否与第一个链表的当前节点相同。这种方法的时间复杂度将为O（M * N），其中m和n是两个列表中的节点数。

方法二(标记已访问的节点)：

此解决方案需要修改基本的链表数据结构。每个节点都有一个visited标志。遍历第一个链表并保持标记已访问的节点。现在遍历第二个链表，如果再次看到已访问的节点，则存在交点，请返回交点节点。此解决方案在O(m + n)中工作，但需要每个节点的额外信息。可以使用哈希实现不需要修改基本数据结构的此解决方案变体。遍历第一个链表并在哈希中存储已访问节点的地址。现在遍历第二个链表，如果看到哈希中已经存在的地址，则返回交点节点。

方法三(使用节点计数的差异)：

获取第一个列表中节点的数量，将其计数为c1。
获取第二个列表中节点的数量，将其计数为c2。
获取计数之差 d = abs(c1 – c2)
现在从第一个节点开始遍历更大的列表，直到d个节点，以便从这里开始两个列表具有相等的节点数
然后我们可以同时遍历两个列表，直到遇到公共节点。（请注意，获取公共节点是通过比较节点的地址完成的）

下图是上述方法的运行过程：

C++程序查找两个链表交点

下面是上述方法的实现：

// 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提供
}