单链表相交的算法

判断两个链表是否相交：（假设两个链表都没有环）
1、判断第一个链表的每个节点是否在第二个链表中
2、把第二个链表连接到第一个后面，判断得到的链表是否有环，有环则相交
3、先遍历第一个链表，记住最后一个节点，再遍历第二个链表，得到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交

如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）
一种O（n）的办法就是（用两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：
bool check(const node* head)
{
if(head==NULL) return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast) return true;
}
return false;
}