找出单链表的中间元素

算法思想：使用两个指针first和second，只是first每次走一步，second每次走两步，这样当second达到链表尾部时，first刚好在链表的中间。

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; 
}