二重円リンクリスト

Question

二重円リンクリストを作成しました。

私は頭にすべてのノードからの距離を知る必要があります。

2つのノードが同じキーと同じ距離を持っている場合、私は、特定のキーを持つノードを削除するか、または取得しなければならないときなので、両方が削除されたか、だ、そうでない場合は頭部に最も近いノードを削除する必要がありますする必要があります。

円形であるので、私は距離を計算する方法がわからない

...

このように、このリンクリストの仕事の挿入。

すべてのノードは、ヘッドの後に行きます。

例：

1）ヘッド

2）ヘッド-A（挿入A）

3）ヘッド-BA（挿入B）

4）ヘッド-CBA（挿入C）今の

は、私は距離なしでのみ、通常のキャンセルをしました。 これは私のコードです。

/* Function to delete node with the key */ 
public void deleteWithKey(int key) { 
    if (key == head.getData()) { 
     if (size == 1) { 
      head = null; 
      end = null; 
      size = 0; 
      return; 
     } 
     head = head.getLinkNext(); 
     head.setLinkPrev(end); 
     end.setLinkNext(head); 
     size--; 
     return; 
    } 
    if (key == end.getData()) { 
     end = end.getLinkPrev(); 
     end.setLinkNext(head); 
     head.setLinkPrev(end); 
     size--; 
    } 
    Node current = head.getLinkNext(); 
    for (int i = 2; i < size; i++) { 
     if (key == current.getData()) { 
      Node p = current.getLinkPrev(); 
      Node n = current.getLinkNext(); 

      p.setLinkNext(n); 
      n.setLinkPrev(p); 
      size--; 
      return; 
     } 
     current = current.getLinkNext(); 
    } 
    System.out.println("Don't exist a node with this key"); 
} 

ありがとうございます。

Answer 1

これは私がやった最後の作業コードです。

改善がありますか？助けのためのすべての

感謝。

複雑= O（N）

/* Function to delete node with the key */ 
public void deleteWithKey(int key) { 
    if (key == head.getData()) { 
     if (size == 1) { 
      head = null; 
      end = null; 
      size = 0; 
      return; 
     } 
     head = head.getLinkNext(); 
     head.setLinkPrev(end); 
     end.setLinkNext(head); 
     size--; 
     return; 
    } 
    if (key == end.getData()) { 
     end = end.getLinkPrev(); 
     end.setLinkNext(head); 
     head.setLinkPrev(end); 
     size--; 
    } 
    Node next = head; 
    Node back = head; 
    while (next != end) { 
     next = next.getLinkNext(); 
     back = back.getLinkPrev(); 
     if ((key == next.getData()) && (key == back.getData()) && (next != back)) { 
      Node p = next.getLinkPrev(); 
      Node n = next.getLinkNext(); 
      Node p1 = back.getLinkPrev(); 
      Node n1 = next.getLinkNext(); 
      p.setLinkNext(n); 
      n.setLinkPrev(p); 
      p1.setLinkPrev(n1); 
      n1.setLinkPrev(p1); 
      size -= 2; 
      return; 
     } 

     if ((key == next.getData()) && (next != back)) { 
      Node p = next.getLinkPrev(); 
      Node n = next.getLinkNext(); 
      p.setLinkNext(n); 
      n.setLinkPrev(p); 
      size--; 
      return; 
     } 
     if ((key == next.getData()) && (next == back)) { 
      Node p = next.getLinkPrev(); 
      Node n = next.getLinkNext(); 
      p.setLinkNext(n); 
      n.setLinkPrev(p); 
      size--; 
      return; 
     } 
    } 
    System.out.println("Don't exist a node with this key"); 
} 

Answer 2

これは私がこの問題を解決すると考えることができ擬似コードです。考えるhead

、

// no data 
if(head==null) return; 
// next and prev are always at same distance 
next = head; 
prev = head.prev; 

// ensure nodes are not same or crossed half way through the list 
while (next == prev || next.prev == prev){ 
// delete nodes if values are same 
if (next.val == prev.val){ 
    if(next!=head) { 
     next.prev.next = next.next; 
     next.next.prev = next.prev; 
     prev.prev.next = prev.next; 
     prev.next.prev = prev.prev; 
    } 
    // list has only two nodes 
    else if(head.next==prev){ 
     head = null; 
     return; 
    // remove head and its prev node 
    else{ 
     head = head.next; 
     head.prev = prev.next; 
     head.prev.next = head 
    } 
} 
// traverse through the list 
next = next.next 
prev = prev.prev 
} 

Answer 3

あなたが実際に距離を知る必要はありません。むしろ、頭に最も近いものを見つける必要があります

それは円形の二重連結リストなので、この作業は簡単です：

1. 一致するノードと出口
を除去する、のいずれかが目標である場合
2. 頭の両方に初期化する、二つの変数aとbを定義
3. 割り当てa = a.nextとb = b.previous
4. ジャンプ2