这道题有多种算法。
算法1：把第一个链表逐项存在hashtable中，遍历第2个链表的每一项，如果能在第一个链表中找到，则必然相交。
static bool JudgeIntersectLink1(Link head1, Link head2)
{
Hashtable ht = new Hashtable();
Link curr1 = head1;
Link curr2 = head2;
//store all the elements of link1
while (curr1.Next != null)
{
ht[curr1.Next] = string.Empty;
curr1 = curr1.Next;
}
//check all the elements in link2 if exists in Hashtable or not
while (curr2.Next != null)
{
//if exists
if (ht[curr2.Next] != null)
{
return true;
}
curr2 = curr2.Next;
}
return false;
}
算法2：把一个链表A接在另一个链表B的末尾，如果有环，则必然相交。如何判断有环呢？从A开始遍历，如果能回到A的表头，则肯定有环。
注意，在返回结果之前，要把刚才连接上的两个链表断开，恢复原状。
static bool JudgeIntersectLink2(Link head1, Link head2)
{
bool exists = false;
Link curr1 = head1;
Link curr2 = head2;
//goto the end of the link1
while (curr1.Next != null)
{
curr1 = curr1.Next;
}
//join these two links
curr1.Next = head2;
//iterate link2
while (curr2.Next != null)
{
if (curr2.Next == head2)
{
exists = true;
break;
}
curr2 = curr2.Next;
}
//recover original status, whether exists or not
curr1.Next = null;
return exists;
}
算法3：如果两个链表的末尾元素相同，则必相交。
static bool JudgeIntersectLink3(Link head1, Link head2)
{
Link curr1 = head1;
Link curr2 = head2;
//goto the end of the link1
while (curr1.Next != null)
{
curr1 = curr1.Next;
}
//goto the end of the link2
while (curr2.Next != null)
{
curr2 = curr2.Next;
}
if (curr1 != curr2)
return false;
else
return true;
}