C语言中的单向链表操作，复杂度为O（1）

Question

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

有问题的操作是：

< li >添加到尾部 < li >从头部移除 < li >返回中间节点

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

    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）复杂度。我的主要想法是，如果我保持对中间节点当前位置的引用，我可以随时跟踪它。这适用于Add-to-tail函数，因为我可以相应地向前移动中间节点。但是，如果去掉头部的话，它就不起作用了，因为我不可能一直向后移动中间的引用，因为它必须是一个单独的链接列表。

我已经得到保证，在 O（1） 中可以做到这一点，并且有人暗示可以这样做的原因是因为这是列表将经历的唯一三个操作，因此中间节点有一个模式可以遵循。

我想不出有什么方法可以做到这一点，除非将从头部到中间节点的每个节点的引用保持为最小值，但有人告诉我，我不需要这样做来实现O（1）。

任何帮助都将不胜感激。

Answer 1

然而，它不工作，与删除头部，因为没有办法，我可以继续向后移动中间的参考

好事情是你不必向后移动中间，然后！去掉头只能让中间往前走。