单链表的数据结构定义如下：
typedef struct node
{
ElemType data;
struct node *next;
}list;
其中，ElemType可以是任意数据类型如int、float或者char等，在算法中，规定其默认为int类型。
二、判断是否相交
链表相交形态：
（1）如果存在交点，则两个链表呈Y字形，而不是X形；
（2）如果存在交点，则两个链表在交点及其之后的部分是重叠的，且长度和数据相同。
判断是否相交的方法有多种，这里分链表本身有无环来介绍：
1、无环
（1）是否有环
原理：把一个链表的尾结点和另一个链表的首结点链接起来，然后判断是否有环（这个原理可以参考前文）即可，具体代码如下：
bool iscross(list *head1, list *head2)
{
if ((NULL == head1) || (NULL == head2))
{
return false;
}
list *p1=head1;
while (p1->next)
{
p1 = p1->next;
}
p1->next = head2;
if (hascircle(head1)) // hascircle函数参考前文，在此直接引用
{
return true;
}
return false;
}
（2）尾结点相等
原理：如果两个链表相交，则其尾结点必然相等（重叠），具体代码如下：
bool iscross(list *head1, list *head2)
{
if ((NULL == head1) || (NULL == head2))
{
return false;
}
while (head1->next)
{
head1 = head1->next;
}
while (head2->next)
{
head2 = head2->next;
}
if (head1 == head2)
{
return true;
}
return false;
}
2、有环
原理：有环链表相交，必然有同一个环，可以用快慢指针解决，即在绕环n圈后，快指针必然遇到慢指针，具体代码如下：
bool iscross(list *head1, list *head2)
{
if ((NULL == head1) || (NULL == head2))
{
return false;
}
bool iscross = false;
list *fast=head1, *slow=head2;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (slow && (slow == fast))
{
iscross = true;
break;
}
}
return iscross;
}
三、求两链表交点
求环的起点原理与求是否有环类似，但需要额外步骤：用两个步长分别为1和2的指针遍历链表，直到两者相遇，此时慢指针走过的长度就是环的长度，相遇后把其中一个指针（比如：步长为2的指针）重新设定为起始点，让两个指针都以步长1再走一遍链表，相遇点就是环的起始点。推理证明步骤如下：
第一次相遇时：
慢指针走过的路程：S1 = 非环部分长度 + 弧A长
快指针走过的路程：S2 = 非环部分长度 + n*环长 + 弧A长
由S1*2 = S2可以得出：非环部分长度 = n*环长 - 弧A长
让指针A回到起始点后，走过一个非环部分长度，指针B走过了相等的长度，也就是n*环长，正好回到环的开头。
如果不能理解这些的话，可以从纯数学的角度来看此问题，即非环部分长度 = n*环长 - 弧A长，那就行了，具体算法如下：
list *findintersection(list *head1, list *head2)
{
if ((NULL == head1) || (NULL == head2))
{
return NULL;
}
list *p1=head1, *p2=head2;
int i=0, j=0, diff=0;
while (NULL != p1->next) // 求链表1的长度
{
p1 = p1->next;
i++;
}
while (NULL != p2->next) // 求链表2的长度
{
p2 = p2->next;
j++;
}
if (p1 != p2) // 相交则尾结点必定相同，否则不相交
{
return NULL;
}
else // 相交则寻找第一个相同的交点
{
p1 = head1;
p2 = head2;
// 使得两个链表的起始位置离尾部的距离一致
if (i >= j)
{
diff = i - j; // 算出两条链表的长度差值
// 长链表的指针向前移动差值个单位
for (int k=0; k
p1 = p1->next;
}
}
else
{
diff = j - i;
// 长链表的指针向前移动差值个单位
for (int k=0; k
p2 = p2->next;
}
}
// 开始比较，如果相等则是第一个交点
while (p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
}
如果无法理解上面的代码，可以看下图：
图1 链表相交
图2 链表相交