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