判斷兩個單鏈表是否相交

這道題有多種算法
算法把第一個鏈表逐項存在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;
}

From:http://tw.wingwit.com/Article/program/sjjg/201405/30738.html