Java鏈表 - 如何複製數據？

我試圖代碼，移動「N」節點的數量在雙向從前面鏈表，並將它們添加到後面的函數：Java鏈表 - 如何複製數據？

public class PetList { 
    protected class LinkNode { 
     protected LinkNode next; 
     protected LinkNode prev; 
     protected Pet animal; // note that my data within a node is an object 

     public LinkNode() { 
      next = prev = null; 
     } 
    } 
    protected LinkNode first; 
    protected LinkNode last; 

    public PetList() { 
     first = last = null; 
    } 
//... 
//... other functions 

public void Rotate(int n) { 

}

現在我知道如何插入一個節點後，例如：

public void insertRear(Pet giraffe) { 
    LinkNode temp = new LinkNode(); 
    temp.animal = new Pet(giraffe); 
    if(first == null) { 
     first = last = temp; 
     return; 
    } 
    temp.prev = last; 
    last.next = temp; 
    last = temp; 
}

但在我的旋轉功能：

public void Rotate(int n)

我沒有一個對象作爲參數。也就是說，如何創建臨時LinkNode並將數據複製到第一個LinkNode的對象中，然後將我的臨時節點移回到後面，刪除我的第一個節點？或者還有另一種更好的方法來做到這一點？謝謝你的幫助。

來源

2017-04-21 Coder117

移動數據與複製數據不同 – efekctive

爲什麼你需要一個對象作爲參數？您已經說過，您只是想將列表中的第一件事物移到最後。 – azurefrog

取第一個節點，將其刪除，將下一個節點標記爲列表的新頭，然後將第一個節點放在末尾。 – njzk2

它應該很簡單。這裏是你如何從頭部移動一個節點到尾：

public void moveHeadToTail() { 
    if (first == null || last == null) { 
     throw new IllegalStateException("can't do that on empty list"); 
    } 
    // Detach the first node 
    LinkNode temp = first; 
    first = temp.next; 
    first.previous = null; 
    temp.next = null; 

    // Put the tmp node at the end 
    last.next = temp; 
    temp.prev = last; 
    last = temp; 
}

然後，您可以拆分成更好的功能：popHead和pushTail：

public LinkNode popHead() { 
    if (first == null) { 
     throw new IllegalStateException("can't do that on empty list"); 
    } 
    LinkNode temp = first; 
    first = temp.next; 
    first.previous = null; 
    temp.next = null; 
    return temp; 
} 

public void pushTail(LinkNode node) { 
    if (last == null) { 
     throw new IllegalStateException("can't do that on empty list"); 
    } 
    last.next = node; 
    node.prev = last; 
    node.next = null; 
    last = node; 
}

，然後使旋轉更容易：

public void moveHeadToTail() { 
    pushTail(popHead()); 
}

然後修改得到它的工作n應該是相當平凡的。

來源

2017-04-21 19:21:25 njzk2

您可以通過一次移動整個塊來執行O（1）中的更新（不包括遍歷）。 – shmosel

「（不包括遍歷）」爲什麼不算遍歷？ – njzk2

您仍然需要遍歷n個元素以查找截斷點，但不需要更新每個元素。 – shmosel

我會從列表開始處切下一段長度爲n的節點，跟蹤切斷列表中的第一個和最後一個節點。將first設置爲切斷子列表後面的節點，使其成爲新的第一個節點。然後，我會通過在舊的最後一個節點和子列表中的第一個節點之間提供鏈接來追加子列表。最後將last設置到子列表的末尾，我就完成了。

將您的節點繪製爲紙上的框，將鏈接繪製爲其他框的箭頭。擦除並繪製可視化步驟。那麼它應該更清晰。

來源

2017-04-21 20:02:07

Java鏈表 - 如何複製數據？

回答

相關問題