鏈接列表的元素

-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

鏈接列表的元素

回答

相關問題