双向链接列表

我创建了双向圆形链接列表。双向链接列表

我需要知道每个节点到头部的距离。

因为当我必须删除或获取一个节点与特定键，如果2个节点具有相同的密钥和相同的距离，两者都必须被删除或获得，否则必须删除最接近头节点。

我不知道如何计算距离，因为是圆形的......

这样这个链表工作的插入。

所有节点后头部去。

实施例：

1）头部

2）头 - 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"); 
}

感谢所有。

来源

2017-05-28 Master-Antonio

为什么它来计算的距离的问题？ –

因为是循环的。每个节点都链接到左侧和右侧。我需要知道从头到每个节点的距离。 –

示例：我有一个列表Head-B-A，B和A的距离相同。因为A与Head关联。将是A <-->头<--> B <---> A –

这是我所做的最终工作代码。

你有没有改进？

感谢所有的帮助。

复杂= 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"); 
}

来源

2017-05-28 14:39:40

这是我能想到的解决问题的伪代码。

鉴于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 
}

来源

2017-05-28 10:44:50

该类的next和prev参数节点可帮助我们滚动节点 –

（项目文本）说，头是插入的第一个节点，并且末尾将始终是为插入模式插入的第二个节点。 –

他们是数据节点。你应该保留两个空指针，这些数据节点只是你的impl代码 –

你其实并不需要知道的距离。相反，你需要找到最接近头的。

因为它是一个循环双向链表，这个任务很简单：

定义两个变量a和b，初始化两个头
如果其中任何一个目标，删除匹配的节点和出口
分配a = a.next和b = b.previous
转到2

来源

2017-05-28 11:29:02 Bohemian

没错。我没有想过。我喜欢这个解决方案。我测试得很快。 –

双向链接列表

回答

相关问题