双循环链表

Question

我创建了一个双循环链表。

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

因为当我必须删除或获取具有特定密钥的节点时，如果两个节点具有相同的密钥和相同的距离，则必须删除或获取这两个节点，否则必须删除最靠近头部的节点。

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

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

所有的节点都去追头。

例：

1）头部

2） 头部A（插入A）

3） 头部B-A（插入B）

4） 头部C-B-A（插入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

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

给定头部，

// 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. 定义两个变量a和b，将两者初始化为head
2. 如果其中一个是目标，请删除匹配的节点并退出
3. 分配a=a.next和b=b.previous
4. 转到2