微信

使用微信服务,更方便

职友集>程序员面试题 > 找出单链表的中间元素

找出单链表的中间元素

2012-12-24 19:58:53 阅读( 204 )

1300人 收藏本页

标签:程序员面试题

算法思想:使用两个指针first和second,只是first每次走一步,second每次走两步:
static Link GetMiddleOne(Link head)
{
Link first = head;
Link second = head;
while (first != null && first.Next != null)
{
first = first.Next.Next;
second = second.Next;
}
return second;
}
但是,这道题目有个地方需要注意,就是对于链表元素个数为奇数,以上算法成立。如果链表元素个数为偶数,那么在返回second的同时,还要返回second.Next也就是下一个元素,它俩都算是单链表的中间元素。
下面是加强版的算法,无论奇数偶数,一概通杀:
static void Main(string[] args)
{
Link head = GenerateLink();
bool isOdd = true;
Link middle = GetMiddleOne(head, ref isOdd);
if (isOdd)
{
Console.WriteLine(middle.Data);
}
else
{
Console.WriteLine(middle.Data);
Console.WriteLine(middle.Next.Data);
}
Console.Read();
}
static Link GetMiddleOne(Link head, ref bool isOdd)
{
Link first = head;
Link second = head;
while (first != null && first.Next != null)
{
first = first.Next.Next;
second = second.Next;
}
if (first != null)
isOdd = false;
return second;
}

来自分智网

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

上一篇:单链表反转

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

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