设为首页 加入收藏

TOP

两个单链表相交,计算相交点
2014-11-24 02:23:03 】 浏览:303
Tags:两个 单链表 相交 计算 交点

分别遍历两个单链表,计算出它们的长度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;
}


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇Oracle数据库面试题汇总 下一篇华为面试心得

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目