职友集>程序员面试题 > 判断两个单链表是否相交

判断两个单链表是否相交

2015-10-20 06:30:02 阅读( 79 )

1044人 收藏本页

标签:程序员面试题

这道题有多种算法。
算法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;
}

来自分智网

下一篇:单链表交换任意两个元素(不包括表头)

上一篇:两个不交叉的有序链表的合并

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题