typedef struct link {
int elem; //表示数据域
struct link* next; //表示指针域
}link;//
在此基础上，判断 2 个单链表是否相交的实现代码为：
//自定义的bool类型
typedef enum bool{
False = 0;
True = 1;
}bool;
//L1和L2表示两个单链表，函数返回值为True表示相交，返回False表示不相交
bool linkIntersect(link* L1, link* L2)
{
link* p1 = L1;
link* p2 = L2;
//遍历L1链表L1的各个节点
while (p1)
{
//遍历L2链表，针对每个p1，依次和p2所指节点做比较
while (p2) {
//p1、p2中记录的就是各个节点的存储地址，直接比较即可
if (p1 == p2) {
return True;
}
p2 = p2->next;
}
p1 = p1->next;
}
return False;
}
通过分析 linkIntersect() 函数的实现过程不难得知，无论 2 个链表是否相交，此实现方式的时间复杂度为 O(n2)。
2) 实际上，第 1 种实现方案还可以进一步优化。结合图 1②，2 个单链表相交有一个必然结果，即这 2 个链表的最后一个节点必定相同；反之，如果 2 个链表不相交，则这 2 个链表的最后一个节点必定不相同。
由此，可以对以上实现代码进行优化：
//L1和L2为2个单链表，函数返回True表示链表相交，返回False表示不相交
bool linkIntersect(link* L1, link* L2)
{
link* p1 = L1;
link* p2 = L2;
//找到L1链表中的最后一个节点
while (p1->next)
{
p1 = p1->next;
}
//找到L2链表中的最后一个节点
while (p2->next)
{
p2 = p2->next;
}
//判断L1和L2链表最后一个节点是否相同
if (p1 == p2) {
return True;
}
return False;
}
显然经过优化，该函数的时间复杂度就缩小为 O(n)。
3) 针对第 1 种实现方案的优化，除了第 2 种方式，还有一种思想。
假设 L1 和 L 2 相交，则两个链表中相交部分节点的数量一定是相等的。如图 2 所示：
可以看到，
L1 和 L2 相交，绿色部分节点为 L1 和 L2 链表的相交部分
。
也就是说，
如果 2 个链表相交，那么它们相交部分所包含的节点个数一定相等
。在此基础上，我们可以这样优化第 1 种实现方案，以图 2 中的 L1 和 L2 为例，从 L1 尾部选取和 L2 链表等长度的一个子链表（也也就是图 3中的 temp 子链表），同时遍历 temp 和 L2 链表，依次判断 2 个遍历点是否相同，如果相同则表明 L1 和 L2相交；反之则不相交。
此实现方案的实现代码如下：
//L1和L2为2个单链表，函数返回True表示链表相交，返回False表示不相交
bool linkIntersect(link* L1, link* L2)
{
link* plong = L1;
link* pshort = L2;
link* temp = NULL;
int num1 = 0, num2 = 0, step = 0;
//得到L1的长度
while (plong) {
num1++;
plong = plong->next;
}
//得到L2的长度
while (pshort) {
num2++;
pshort = pshort->next;
}
//重置plong和pshort，使plong代表较长的链表，pshort代表较短的链表
plong = L1;
pshort = L2;
step = num1 - num2;
if (num1 < num2) {
plong = L2;
pshort = L1;
step = num2 -num1;
}
//将temp指向与pshort相同的那个节点
temp = plong;
while (step) {
temp = temp->next;
step--;
}
//逐个作比较temp和short链表的节点是否相同
while (temp && pshort) {
//可以比较指向指针地址是否相同相同
if (temp == pshort) {
return True;
}
temp = temp->next;
pshort = pshort->next;
}
return False;
}
相比第 2 种方案，此方法的实现逻辑虽然复杂，但优点是，该方法可以找到 2 个单链表相交的交点（也就是相交时的第一个节点），也就是使 linkIntersect() 函数返回 True 时的 temp 指针指向的那个节点。另外，此方案的时间复杂度也为 O(n)。
总结 总的来说，本节讲解了 3 种“判断 2 个链表是否相交”的方法，其中第 2、3 种方案的时间复杂度都比第 1 种要小。 从另一个角度比较这 3 种方案，第 1 种和 第 3 种在判断“2 个链表是否相交”的同时，还能找到它们相交的交点，而第 2 种实现方案则不具备这个功能。 如果读者想实现“判断 2 个链表是否相交，如果相加找到交点”这样的功能，只需对第 1、3 种方案的实现代码做略微调整即可。由于很简单，读者可自行尝试实现。
