c++ - C++ 中复杂度为 O(1) 的单链表操作

Question

我需要制作一个可以进行三个操作的链表。所有这三个操作都必须具有 O(1) 复杂度。

有问题的操作是:

• 添加到尾部
• 从头部移除
• 返回中间节点

正在使用的节点结构如下:

    struct node {
        int data;
        node* link;

        node(int input) {
            data = input;
            link = NULL;
        } 
    };

为了移除头部，我仅通过通常引用头部节点就实现了 O(1)

    if (head != NULL) {
         if (head->link == NULL) {
            delete head;
            head = NULL;
            tail = NULL;
         }
         else {
            node* temp = head;
            head = head->link;
            delete temp;
         }
    }

为了添加到尾部，我通过引用尾部节点实现了 O(1)

    if(head != NULL) {
         tail->link = new node(input);
         tail = tail->link;
    }
    else {
         head = new node(input);
         tail = head;
    }

我的问题是返回中间节点。我知道如何通过遍历列表来做到这一点，但这意味着它将具有 O(n) 复杂性。我的主要想法是，如果我保留对中间节点当前位置的引用，我就可以随时跟踪它。这适用于添加到尾部功能，因为我可以相应地向前移动中间节点。然而，移除头部是行不通的，因为我无法继续向后移动中间引用，因为它必须是一个单链表。

我确信可以在 O(1) 中完成此操作，并且有人暗示它可以完成的原因是因为这是列表将经历的仅有的三个操作，因此存在一个模式中间节点跟随。

我想不出有什么方法可以做到这一点，除非至少保留对从头部到中间节点的每个节点的引用，但有人告诉我不需要这样做来实现 O( 1).

任何帮助将不胜感激。

Answer 1

It doesn't work, however, with removing the head as there is no way I can keep moving the middle reference backwards

幸好你不必向后移动中间部分!去掉头部只能让中间往前走。