給出一個節點我怎麼能找到一個節點在一個單向鏈表

Question

鑑於目前的節點，我怎麼能找到它以前在單鏈表節點。謝謝。邏輯會做，代碼表示讚賞。我們都知道給根節點人能做到連續進給，我想知道是否有避免順序訪問開銷更聰明的方式。 （假設沒有對根節點的訪問）謝謝。

Answer 1

你不能。

按定義，單鏈表僅將每個節點鏈接到其後繼者，而不是前驅者。沒有關於前任的信息;甚至沒有關於它是否存在的信息（你的節點可能是列表的頭部）。

你可以使用一個雙向鏈表。 你可以嘗試讓你擁有前身傳遞進來擺在首位的參數重新排列的一切。

您可以掃描整個堆尋找一個看起來像前驅節點的記錄，並指向您的節點。 （不是一個嚴肅的建議。）

Answer 2

從頭開始瀏覽列表，直到遇到一個節點，其節點鏈接指向您的當前節點爲next。

但是，如果你需要這樣做，也許你不應該使用單向鏈表。

Answer 3

假設你正在談論一個前向單鏈表（每個節點只有一個指向'下一個'等），你將不得不迭代從列表的開始，直到你找到有'下一個'等於您當前的節點。顯然，這是一個緩慢的操作。

希望這會有所幫助。

Answer 4

你只對一個單向鏈表的選擇是一個線性搜索，類似下面（Python的仿僞碼）：

find_previous_node(list, node): 
    current_node = list.first 
    while(current_node.next != null): 
     if(current_node.next == node): 
      return current_node 
     else: 
      current_node = current_node.next 
    return null 

Answer 5

假設你使用着單向鏈表你的代碼看起來應該像

while(node) 
{ 
     previous = node 
     node = node.next 
     // Do what ever you want to do with the nodes 
} 

Answer 6

使用nodeAt（）方法並傳遞當前節點的頭部，大小和索引。

public static Node nodeAt(Node head,int index){ 
    Node n=head; 
    for(int i=0;i<index;i++,n=n.next) 
     ; 
    return n; 
    } 

其中n返回前驅節點。

Answer 7

這是某種形式的黑客，我發現了，而現在，這裏解決問題（刪除列表中的每一個偶數節點）

internal void DeleteNode(int p) 
    { 
     DeleteNode(head, p); 
    } 

    private void DeleteNode(Node head, int p) 
    { 
     Node current = head; 
     Node prev = null; 

     while (current.next != null) 
     { 
      prev = current; 
      current = current.next; 
      if (current.data == p) 
      { 
       prev.next = current.next; 
      } 
     } 
    } 

，在上一個分配電流，然後將電流下一個從而prev包含前一個節點。 希望這有助於...

Answer 8

這裏有一個小竅門與線性搜索：只是通過在節點或者其前面的節點，則它的位置正在尋找：

private MyNode findNode(int pos) { 
//node will have pos=pos-1 
     pos-- = 1; 
     MyNode prevNode = null; 
     int count = 0; 
     MyNode p = first.next; // first = head node, find it however you want. 
//this is for circular linked list, you can use first!=last for singly linked list 
     while (p != first) { 
      if (count == pos) { 
       prevNode = p; 
       break; 
      } 
      p = p.next; 
      count++; 
     } 
     return prevNode; 
    } 

Answer 9

Node* temp = head; 
Node* prev = head; 
while(temp !=null && temp->data==key){ 
    prev = temp; 
    temp = temp->next 
}