在数据结构中，单链表是一种常见的数据表示形式，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。在实际应用中，我们可能会遇到需要判断两个单链表是否相交的问题。
一、问题分析
判断两个单链表是否相交，关键在于确定它们是否存在一个共同的节点。这里需要注意的是，相交并不意味着两个链表的起始节点相同，而是指在某个节点之后，两个链表的部分节点是共享的。
为了解决这个问题，我们可以采用以下几种方法：
暴力法：遍历第一个链表中的每个节点，然后检查该节点是否存在于第二个链表中。这种方法的时间复杂度较高，为O(n*m)，其中n和m分别是两个链表的长度。
哈希表法：将第一个链表的所有节点存储在一个哈希表中，然后遍历第二个链表，检查每个节点是否存在于哈希表中。这种方法的时间复杂度为O(n+m)，但需要额外的空间来存储哈希表。
双指针法（又称“长度差法”）：首先计算两个链表的长度，然后让长链表的前导指针先移动长度差步，接着同时移动两个链表的指针，检查它们是否会在某个时刻相遇。如果相遇，则两个链表相交；否则，不相交。这种方法的时间复杂度为O(n+m)，且不需要额外的空间。
二、算法思路与C++代码实现
在这里，我们选择双指针法来实现判断两个单链表是否相交的算法。
算法思路：
遍历两个链表，分别计算它们的长度。 根据长度差，让较长链表的头指针先移动相应的步数。 同时移动两个链表的指针，检查它们是否会在某个时刻指向同一个节点。
C++代码实现：
#include <iostream>
// 定义链表节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 获取链表长度
int getLength(ListNode* head) {
int length = 0;
while (head != nullptr) {
length++;
head = head->next;
}
return length;
}
// 判断两个链表是否相交
bool isIntersect(ListNode* headA, ListNode* headB) {
// 计算两个链表的长度
int lenA = getLength(headA);
int lenB = getLength(headB);
// 让长链表的头指针先移动长度差步
ListNode* pA = headA;
ListNode* pB = headB;
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
pA = pA->next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
pB = pB->next;
}
}
// 同时移动两个链表的指针，检查是否相遇
while (pA != nullptr && pB != nullptr) {
if (pA == pB) {
return true; // 链表相交
}
pA = pA->next;
pB = pB->next;
}
return false; // 链表不相交
}
int main() {
// 创建两个相交的链表
ListNode* common = new ListNode(8);
ListNode* c2 = new ListNode(4);
common->next = c2;
ListNode* headA = new ListNode(3);
ListNode* a2 = new ListNode(1);
headA->next = a2;
a2->next = common;
ListNode* headB = new ListNode(99);
ListNode* b2 = new ListNode(1);
headB->next = b2;
b2->next = common;
// 判断两个链表是否相交
if (isIntersect(headA, headB)) {
std::cout << "The two linked lists intersect." << std::endl;
} else {
std::cout << "The two linked lists do not intersect." << std::endl;
}
// 释放内存（这里省略了链表的完整释放过程，实际使用时需要注意内存管理）
return 0;
}
代码说明：
我们首先定义了一个链表节点结构 ListNode，并实现了一个构造函数来初始化节点。getLength函数用于计算链表的长度。isIntersect函数实现了判断两个链表是否相交的算法。它首先计算两个链表的长度，然后根据长度差移动长链表的头指针。接着，同时移动两个链表的指针，并检查它们是否会在某个时刻相遇。在 main函数中，我们创建了两个相交的链表，并调用isIntersect函数来判断它们是否相交。最后，输出判断结果。
需要注意的是，在实际应用中，我们需要考虑内存管理问题，特别是在动态分配内存时。为了简化示例，这里省略了链表的完整释放过程。在实际使用时，我们应该在适当的位置释放分配的内存，以避免内存泄漏。
