题意说明
链表取中值,要求: 不用size(),只允许遍历一次…… 取出链表中间结点的值。
问题ps.偶数个怎么处理?——计算机科学里,对于偶数个数的集合,取中间两值的左值即为中值。
思路用两个指针,一个在前面遍历,一个在后面遍历,快的一次跳两次,慢的一次跳一次,总共只遍历一次链表。
数据结构为避免“开挂”,我们干脆不用Java内置的java.util,LinkedList,自己写一个。 下面的是一个极其简单极其简单的一个链表:
class Node {
T element;
Node next