微信

使用微信服务,更方便

职友集>程序员面试题 > 两个单链表相交,计算相交点

两个单链表相交,计算相交点

2014-10-08 06:30:01 阅读( 63 )

436人 收藏本页

标签:程序员面试题

分别遍历两个单链表,计算出它们的长度M和N,假设M比N大,则长度M的链表先前进M-N,然后两个链表同时以步长1前进,前进的同时比较当前的元素,如果相同,则必是交点。
public static Link GetIntersect(Link head1, Link head2)
{
Link curr1 = head1;
Link curr2 = head2;
int M = 0, N = 0;
//goto the end of the link1
while (curr1.Next != null)
{
curr1 = curr1.Next;
M++;
}
//goto the end of the link2
while (curr2.Next != null)
{
curr2 = curr2.Next;
N++;
}
//return to the begining of the link
curr1 = head1;
curr2 = head2;
if (M > N)
{
for (int i = 0; i < M – N; i++)
curr1 = curr1.Next;
}
else if (M < N)
{
for (int i = 0; i < N – M; i++)
curr2 = curr2.Next;
}
while (curr1.Next != null)
{
if (curr1 == curr2)
{
return curr1;
}
curr1 = curr1.Next;
curr2 = curr2.Next;
}
return null;
}

来自分智网

下一篇:用链表模拟大整数加法运算

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

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

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