GESP 五级 · GESP202609 C++ 五级 第 1 题

小杨用单链表保存任务序列，并同时维护头指针 head 和尾指针 tail 。在链表非空且已知 tail 的情况 下，在表尾插入新结点的时间复杂度是（　　）。

struct Node {
int value;
Node *next;
};
Node *head;
Node *tail;

A. B. C. D.

看到"尾插"和"已知 tail"，立刻想到不需要遍历链表。关键观察是 tail 直接指向最后一个节点。插入新节点只需：分配内存、设置 next 为 nullptr、修改 tail->next 为新节点、更新 tail 为新节点。每一步都是常数时间操作。因此时间复杂度为 O(1)。

选项 C 是典型错误，源于学生默认链表操作都要遍历。选项 B 和 D 是干扰项，考察对复杂度的直觉。题目最阴险的细节是"已知 tail"，这直接排除了遍历的可能性。

考纲定位

本题考查 GESP 五级《数据结构与算法》模块中单链表操作与时间复杂度分析。命题人卡住的是"指针已知的操作无需遍历"这一核心直觉——五级考生最容易在链表题上犯"看到链表就默认要遍历"的惯性错误，这道题就是专门测试你是否真正理解指针语义。

解题思维

看到"尾插"和"已知 tail"，立刻想到不需要遍历链表。关键观察是 tail 直接指向最后一个节点。插入新节点只需四步：

1. 分配内存：new Node 2. 设置新节点 next：newNode->next = nullptr 3. 修改 tail 的 next：tail->next = newNode 4. 更新 tail 指针：tail = newNode

每一步都是常数时间操作，与链表长度 n 完全无关。因此时间复杂度为 O(1)。