双向循环链表

Question

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

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

因为当我必须删除或获取具有特定键的节点时，如果2个节点具有相同的键和相同的距离，则都必须删除或获取，否则必须删除最接近头部的节点。

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

这个Linked List的插入是这样的。

所有节点都在 Head 之后。

示例：

1) 头

2) Head-A (插入A)

3) Head-B-A (插入B)

4) Head-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

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

给定 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 2

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

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

定义两个变量a和b，将两者初始化为head
如果其中一个是目标，删除匹配的节点并退出
分配 a = a.next 和 b = b.previous
转到 2

Answer 3

这是我完成的最终工作代码。

你有进步吗？

感谢大家的帮助。

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

双向循环链表

Doubly Circular Linked List

java

list

distance

circular-list

doubly-linked-list