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

Question

我需要制作一个可以进行三次操作的链表。这三个操作的复杂度必须为0(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;
    }

我的问题是返回中间节点。我知道如何通过遍历列表来做到这一点，但这意味着它的复杂度是0 (n)我的主要想法是，如果我保持对中间节点当前位置的引用，我就可以随时跟踪它。这适用于Add to tail函数，因为我可以将中间节点向前移动。它不起作用，然而，删除头部，因为没有办法我可以继续移动中间引用向后，因为它必须是一个单链表。

我确信可以在0(1)内完成此操作，并且已经暗示可以这样做的原因是因为这是列表将经历的仅有的三个操作，因此中间节点可以遵循一个模式。

我想不出任何方法可以做到这一点，除非保持对从头部到中间节点的每个节点的引用作为最小值，但是已经被告知我不需要这样做来实现O(1)。

Answer 1

它不起作用，然而，删除头部，因为我无法继续向后移动中间引用

还好你不用把中间向后移动!删除头部只能使中间向前。