链表实现队列的O(n)复杂度优化：如何达成O(1)入队出队？

完全可以通过维护额外的头尾双指针，让链表队列的入队、出队以及获取尾元素操作都达到**O(1)**的时间复杂度，解决你现在需要遍历链表的问题。

核心方案：头尾双指针定位 #

普通单链表只存头指针时，找尾节点必须遍历整个链表，但如果同时维护两个指针：

• head：指向队列的第一个元素（出队操作的目标节点）
• tail：指向队列的最后一个元素（入队操作的目标节点）

就能直接定位首尾，无需遍历。

各操作的O(1)实现 #

1. 入队操作

   • 创建新节点，将tail的next指向新节点
   • 把tail直接更新为新节点
   • 如果队列为空，head和tail同时指向新节点

2. 出队操作

   • 取出head节点的值
   • 将head更新为原head的next节点
   • 如果出队后head为空（队列变空），同步把tail设为空，避免野指针
   • 释放原head节点的内存（根据所用语言的内存管理规则处理）

3. 获取尾元素

   • 直接返回tail指向节点的值即可，完全不需要遍历链表

伪代码示例 #

// 节点结构
struct Node {
    int value;
    Node* next;
};

// 队列结构，维护头尾指针
struct Queue {
    Node* head;
    Node* tail;
};

// 入队函数
void enqueue(Queue* q, int val) {
    Node* newNode = new Node{val, nullptr};
    if (q->tail == nullptr) { // 处理空队列情况
        q->head = newNode;
        q->tail = newNode;
    } else {
        q->tail->next = newNode;
        q->tail = newNode;
    }
}

// 出队函数
int dequeue(Queue* q) {
    if (q->head == nullptr) {
        throw "Queue is empty"; // 空队列异常处理
    }
    int val = q->head->value;
    Node* temp = q->head;
    q->head = q->head->next;
    delete temp;
    if (q->head == nullptr) { // 队列变空，尾指针同步置空
        q->tail = nullptr;
    }
    return val;
}

// 获取尾元素函数
int getTail(Queue* q) {
    if (q->tail == nullptr) {
        throw "Queue is empty";
    }
    return q->tail->value;
}

这种双指针的链表队列，不仅能和数组队列一样实现O(1)的核心操作，还能避免数组队列的扩容开销和固定容量限制，空间利用率更灵活。

内容的提问来源于stack exchange，提问作者user22873067