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

在编写程序时，我们可能需要处理两个链表的交点问题，因为链表可能会在某个节点这交叉在一起。本文将介绍如何查找两个链表的交点，涉及到算法、数据结构和C++程序设计。

链表的基本知识

在开始查找两个链表的交点之前，我们先回顾一下链表的基本知识，因为这些知识是理解和处理交点问题的基础。

链表是一种数据结构，用于存储一系列元素，每个元素称为节点（node）。节点由两部分组成：一个存储数据的域（data field）和一个指向下一个节点的指针（next pointer）。因为链表的元素可以动态增删，所以在链表中每个节点的大小可以不同。链表中的第一个节点称为头节点（head），通常不存储数据。如果链表中只存在一个节点，则该节点即为头节点。

链表的两种常见类型是单向链表（singly linked list）和双向链表（doubly linked list）。单向链表的节点只包含一个指向下一个节点的指针，而双向链表的节点既包含一个指向下一个节点的指针，也包含一个指向前一个节点的指针。

查找两个链表交点的算法

如果两个链表没有交点，则它们在某个时刻会同时到达链表尾部，此时两个链表的长度差应该是相同的。如果两个链表有交点，则从交点开始，两个链表重合成为一个链表，直到链表尾部。

考虑两个链表交点的位置问题。如果两个链表长度相同，则可以同时遍历两个链表，直到发现第一个交点。如果两个链表长度不同，则需要找到一个列表长度差值。为了实现这一点，我们需要在两个链表上跑两遍扫描，一次计算出它们的长度。然后我们平移较长链表的指针，直到两个指针对齐，然后同时扫描两个链表，直到找到第一个交点。

下面给出查找两个链表的交点算法的核心代码。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *p1 = headA, *p2 = headB;
    while (p1 != p2) {
        p1 = p1 ? p1->next : headB;
        p2 = p2 ? p2->next : headA;
    }
    return p1;
}

首先，我们初始化两个指针p1和p2，分别指向链表headA和headB的头节点。然后，我们同时遍历这两个链表，并比较指针p1和p2是否相等。如果它们相等，则表示已经找到了交点，返回p1。如果它们不相等，则将它们分别指向自己当前节点的下一个节点，直到它们重合或者都为NULL。

示例

为了演示以上算法，我们可以使用以下两个链表：

ListNode *headA = new ListNode(4);
ListNode *a1 = new ListNode(1);
ListNode *a2 = new ListNode(8);
ListNode *a3 = new ListNode(4);
ListNode *a4 = new ListNode(5);
headA->next = a1;
a1->next = a2;
a2->next = a3;
a3->next = a4;
a4->next = NULL;

ListNode *headB = new ListNode(5);
ListNode *b1 = new ListNode(0);
ListNode *b2 = new ListNode(1);
headB->next = b1;
b1->next = b2;
b2->next = a2;

上述代码中，链表headA包含5个节点（4 -> 1 -> 8 -> 4 -> 5），链表headB包含4个节点（5 -> 0 -> 1 -> 8 -> 4 -> 5）。链表headB的最后一个节点指向链表headA的第三个节点，所以它们的交点为节点8。

现在我们可以使用上面的函数来查找两个链表的交点：

ListNode *intersection = getIntersectionNode(headA, headB);
if (intersection != NULL) {
    cout << "The intersection node is: " << intersection->val << endl;
} else {
    cout << "The linked lists do not intersect." << endl;
}

在本例中，程序将输出以下消息：