查找單鏈接列表中的第3個最後一個元素 - 算法

我在思考Algo以找到單鏈接列表中的第3個最後一個元素，我自己想出了一個（空間高效）
將ArrayList中的鏈表使用時間複雜度爲O（n）的循環[很多空間複雜度]
然後找到Arraylist的大小並在（size-2）索引位置檢索元素[required element] 請指導我如果我的算法中意義查找單鏈接列表中的第3個最後一個元素 - 算法

FYI
其他我搜索是：把兩個指針，並保持1指針3日的Elemen第1個要素和第二指針上t並將它們並行移動
當第二個指針到達LinkList的末尾時，檢索第一個指針指向的節點[必需節點]

來源

2013-07-05 Java Geek

參見：http://stackoverflow.com/questions/460137/algorithm-to-find-the-pointer-to-the-node-m-steps-to-tail-in-a-singly- linked-lis – maybeWeCouldStealAVan

您可以使用單個指針。遍歷直到'ptr.next（）。next（）。next（）== null'; – GriffeyDog

@GriffeyDog由於'遍歷'是一系列'.next（）'調用，所以你只需要進行三次遍歷，只需要一次。但是，由於緩存，您的方法可能會比三次單獨的遍歷更快。 – maybeWeCouldStealAVan

使用兩個指針：pointer-1和pointer-2

使pointer-1指向單鏈表中的第三個節點。

pointer-1 = node1->next->next; // point to 3rd nd 

node1-->node2-->node3-->node4---> ...... -->node-last 
       ^
       | 
       pointer-1

現在設置pointer-2點（每次第一個節點

pointer-2 = node1; // point to 1st nd 

node1-->node2-->node3-->node4---> ...... -->node-last 
^   ^
    |    | 
    pointer-2  pointer-1

現在，旅遊鏈表在一個循環，直到pointer-1點到最後一個節點，在迴路還更新指針-2到自身下一個節點）

while (pointer-1->next!=NULL){// points to last node 
    pointer-1 = pointer-1 -> next; 
    pointer-2 = pointer-2 -> next; 
} 

When loop ends pointer-1 points to last-node, pointer-2 points to third last 

node1-->node2-->........ ->node-l3-->node-l2-->node-last 
          ^    ^
          |     | 
          pointer-2   pointer-1

它工作s在O（n）次，其中n是鏈接列表中的節點數。

來源

2013-07-05 15:26:03

由於鏈接列表是單鏈接的，因此您需要從從開始到結束才知道第三個到最後一個元素是什麼，操作系統O(n)時間是不可避免的（除非你保持一個指向鏈表中倒數第三個元素的指針）。

你的2個指針的想法，將使用恆定的空間。這可能是更好的選擇，因爲創建一個ArrayList會有更多的開銷，並使用更多的空間。

來源

2013-07-05 15:21:42 jh314

獲取兩個指針。 PA，PB 移動pA的3個元素提前和PB的頭：

1->2->3->4-> .... ->99->100 
|  | 
pB pA

在此之後，在同一迴路移動兩個指針，直到pA的到達最後一個元素。

在這點PB將指向最後3元

1->2->3->4-> .... ->98->99->100 
        |  | 
        pB  pA

編輯：遍歷將是一個：

while(pA->next!=null){ 
    pA = pA->next; 
    pB = pB->next; 
}

這裏的pB將是第三個最後

來源

2013-07-05 15:23:16 Elbek

這將需要兩次遍歷。 – maybeWeCouldStealAVan

一遍遍，不是兩遍。您將在一個foreach中移動兩個指針 – Elbek

這仍然是兩次遍歷，一起完成。最好保存三個值，以便不需要遍歷兩個指針或再次遍歷來查找結果。 – maybeWeCouldStealAVan

另一種觀點來解決這個即使它是O（n）

創建一個空的陣列（n）時，從0開始一個指針到該陣列中，並從鏈接列表的開頭開始，以及。每次訪問節點時，都會將其存儲在數組的當前索引中，並推進數組指針。繼續填充數組中的節點，當到達數組末尾時，請再次從頭開始以覆蓋。現在，一旦你結束列表的最後一個指針第n elemtn從結尾:)

來源

2013-07-05 15:33:27 neoeahit

在實踐中，Java LinkedList保持跟蹤其大小，所以你可以去'list.get（list.size（）-2）'，但與一個構造的鏈表，我會做以下幾點：

保持一個3值的數組。在遍歷列表時，請在array[i%3]處添加更新值。當沒有更多的值時，返回值爲array[(i-2)%3]。

來源

2013-07-05 15:38:33 maybeWeCouldStealAVan

我要做的第一件事就是要求你重新考慮你對一個單獨鏈表的使用。爲什麼不將數據存儲在ArrayList中？它完成了你似乎想要的一切，它是一個內建的，所以它比大多數人寫的要高效。

如果你被綁定並確定使用鏈表，我建議保留一個直接指向最後一個元素（tle）的第三個元素。插入是很容易的 - 如果它們來到這些之前，什麼也不做;如果在之後，將tle指針前進到tle的下一個。清除更麻煩，但可能不是大部分時間。如果去除之前發生，它仍然是問題。令人討厭的情況是，如果要移除的元素是tle或更新的元素，在這種情況下，您可以從開始迭代到當前節點的下一個（）引用是tle。當前節點將成爲新的節點，然後您可以繼續進行刪除。由於只有三個節點調用這個級別的工作，所以如果這個列表很大，你可能大部分時間都會做得很好。

最後一個選項，如果從最後清除頻繁發生，就是從後向前維護您的列表。然後，爲了維護目的，這些信息從前面變成了第三個。

來源

2013-07-05 16:07:46 pjs

//We take here two pointers pNode and qNode both initial points to head 
    //pNode traverse till end of list and the qNode will only traverse when difference 
    // between the count and position is grater than 0 and pthNode increments once 
    // in each loop 
    static ListNode nthNode(int pos){ 
    ListNode pNode=head; 
    ListNode qNode=head; 
    int count =0; 
    while(qNode!=null){ 
     count++; 
     if(count - pos > 0) 
      pNode=pNode.next; 
     qNode=qNode.next; 
    } 
    return pNode; 
}

來源

2014-08-25 13:12:54 Rohit

查找單鏈接列表中的第3個最後一個元素 - 算法

回答

相關問題