链接列表的元素

-1

有人可以请解释在Java中，你如何找到一个链接的中间元素单通？链接列表的元素

我已经使用了它，但似乎无法找到关于如何对其进行编码的简单解释。

2014-10-16 user3187763

我想谷歌没有答案，因为这个问题是微不足道的。列表有一个'get（int position）'。另外，如果你在中间运行，你不想使用LinkedList。 – Felk 2014-10-16 23:51:53

-2

由于它是一个LinkedList，所以直到第一次（也是唯一一次）通过之后，您将无法找到它的大小。要找到中间元素，你需要知道两件事情;中间的索引是什么，该索引处的元素的值是多少。找到中间索引是很容易的 - 只需在列表中通过一次，就可以计算出有多少个节点。当你这样做时，你需要跟踪单独数据结构中的每个元素，可能是一个ArrayList，因为你只允许一个通过LinkedList传递。完成后，计数器的一半找到中间索引，然后返回该索引处的ArrayList元素。

伪代码如下所示：

int count 
ArrayList elements 

for each node in LinkedList: 
    count++ 
    elements.append(node) 

middleIndex = count/2 
middleElement = elements.getIndex(middleIndex) 

return middleElement

当然，你需要采取了这样的情况，其中没有一个单一的中间元素。

来源

2014-10-17 00:01:02 ubervillain

直到您记得任何理智的实现缓存了元素的数量。 – 2014-10-17 00:04:36

像Java的'LinkedList'确实... :) – Krease 2014-10-17 00:05:05

并将'LinkedList'复制到'ArrayList'只是为了找到中间元素有点击败目的... – Krease 2014-10-17 00:07:02

LinkedList<String> list = new LinkedList<>(); 
list.add("foo"); 
list.add("bar"); 
list.add("baz"); 
String middle = list.get(list.size()/2); 
System.out.println(middle); // bar

分配middle的get通话期间将通过列表的一半呼叫。

正如在评论中指出的那样，中间是在LinkedList上操作的最差的地方。考虑使用另一种变体，如ArrayList。

来源

2014-10-17 00:01:41 Krease

我认为这是一个你可能在面试问题列表中看到的一种诡计问题。

一个解决方案是使用两个指针来遍历列表，一个采取两个步骤，一个采取一个步骤。

当每次两步走的指针到达列表的末尾时，只走一步的指针会到达一半。

我怀疑这种做法是否真的有用，虽然..

祝你好运！

来源

2014-11-22 16:38:59 user1634700

链接列表的元素

回答

相关问题