前言单链表是最基础的手写数据结构每个节点保存一个值和指向下一个节点的指针节点在内存中不必连续。它适合频繁在头部插入删除、或者需要在遍历中「摘除」节点的场景代价是不能随机访问查找第 k 个元素要从头走。自己实现单链表难点不在「怎么连指针」而在边界与所有权头指针为空时怎么插入、删除尾节点后尾指针指向哪里、析构时会不会漏掉节点、拷贝对象时会不会两个链表共用同一批节点导致重复释放。这些问题在 LeetCode 的裸指针接口里往往被隐藏在真实工程里却必须处理。本文实现一个带head、tail、size三个成员的链表类覆盖头插、尾插、按位置插入、按位置删除、查找、反转、清空以及析构、拷贝、移动。代码以 C17 为准使用裸指针new/delete是为了讲清所有权工程代码可以用std::unique_ptr串联节点避免手写析构。一、节点设计与类的不变量节点只需要两个字段值、下一个节点的指针。把节点定义在链表类的私有区域外部只能通过链表的接口操作避免调用方直接改next破坏结构。链表类维护三个成员成员含义不变量head_头节点指针空表时为nullptrtail_尾节点指针空表时为nullptr非空时tail_-next nullptrsize_节点个数与从头遍历得到的节点数一致这三个不变量是实现的「合同」。每次插入删除后都要检查空表时head_与tail_是否同时为空非空时tail_是否真的指向最后一个节点size_是否与节点数一致。很多 bug 不是指针写错而是某次操作后不变量被破坏后续操作在错误状态上继续执行。size_让size()变成 O(1)代价是每次插入删除都要维护。如果不需要常数时间取长度也可以省掉它遍历计数但那样每次取长度都是 O(n)。二、插入先接后断别丢链头插最简单新节点的next指向当前head_再让head_指向新节点。如果原表为空还要把tail_也指向新节点。顺序不能反先让head_指向新节点再设置新节点的next就会把原来的整条链表丢掉。尾插分两种情况。空表时新节点既是头也是尾head_、tail_都指向它。非空时把tail_-next指向新节点再更新tail_。这里不需要遍历因为尾指针已经保存了最后一个节点这也是维护tail_的意义。按位置插入的合法位置是[0, size]pos 0等价于头插pos size等价于尾插中间位置要先走到pos-1个节点令新节点的next指向prev-next再令prev-next指向新节点。这两步的顺序同样不能反先改prev-next新节点就找不到原来的后继了。用文字表示中间插入插入前prev - current插入后prev - node - current步骤node-next prev-next; prev-next node;size_在插入成功后加一。若new抛出std::bad_alloc链表保持原状因为我们在分配成功后才修改指针。三、删除先保存再摘除最后释放删头保存head_让head_指向head_-next释放旧头。如果删除后size_变为 0必须把tail_置空否则tail_会指向已释放的节点成为悬垂指针。删中间或尾部走到待删节点的前驱prev保存victim prev-next令prev-next victim-next。如果victim tail_说明删的是尾节点要更新tail_ prev。最后delete victimsize_减一。顺序的关键是「先保存待删节点再改指针最后释放」。如果先delete再访问victim-next就是释放后使用属于未定义行为undefined behavior, UB可能读到垃圾值也可能崩溃。删除操作的合法性pos必须小于size_。越界时返回 false不做任何修改。空表删除直接返回 false不要解引用空指针。四、资源管理、常用操作与完整实现析构要释放所有节点。从头节点开始先用next保存后继再delete当前节点最后把head_、tail_置空、size_归零。不能直接delete head_了事那样只会释放第一个节点后面的全部泄漏。拷贝构造不能只复制head_指针否则两个链表共用同一批节点任一析构都会让另一个悬垂随后重复释放。正确做法是深拷贝遍历源链表对每个值调用push_back得到一批独立节点。拷贝赋值要处理自赋值和旧资源释放。推荐拷贝并交换copy-and-swap先按值得到一个临时副本再与*this交换三个成员临时对象析构时释放旧链。这样既处理了自赋值也提供了较强的异常安全保证。移动构造直接「偷」走三个成员并把源对象置为空表。移动赋值先释放自身资源再接管源对象的指针。移动后源对象处于「有效但未指定」状态本文的实现把它明确置为空表调用方仍可安全地析构或重新赋值。如果一个类手动管理资源析构、拷贝构造、拷贝赋值通常要一起定义这就是「规则三」C11 之后再加上移动构造与移动赋值称为「规则五」。更好的做法是「零规则」用std::unique_ptr或标准容器管理资源不手写这些函数。本文手写是为了展示原理。反转与查找反转用三个指针prev、cur、next。每次先用next保存cur-next再让cur-next prev然后prev cur、cur next。循环结束时prev是新的头head_ prev。原来的头变成新的尾所以进入循环前要记下tail_ head_空表时tail_保持空。反转过程中不能先改cur-next再保存后继否则会丢失剩余链表。三指针的顺序是「存后继、改指向、推进」。查找返回指向节点值的指针找不到返回nullptr。提供const与非const两个重载const版本返回const int*避免调用方通过常量链表修改元素。返回指针而不是值是为了让调用方能区分「找到 0」和「没找到」如果返回值类型0会和失败混淆。完整实现// 适用于 C17#include cstddef#include iostream#include utilityclass SinglyList {public:SinglyList() default;~SinglyList() {clear();}SinglyList(const SinglyList other) {for (Node* p other.head_; p ! nullptr; p p-next) {push_back(p-value);}}SinglyList operator(const SinglyList other) {if (this ! other) {SinglyList temp(other);swap(temp);}return *this;}SinglyList(SinglyList other) noexcept: head_(other.head_), tail_(other.tail_), size_(other.size_) {other.head_ nullptr;other.tail_ nullptr;other.size_ 0;}SinglyList operator(SinglyList other) noexcept {if (this ! other) {clear();head_ other.head_;tail_ other.tail_;size_ other.size_;other.head_ nullptr;other.tail_ nullptr;other.size_ 0;}return *this;}void push_front(int value) {Node* node new Node{value, head_};head_ node;if (tail_ nullptr) {tail_ node;}size_;}void push_back(int value) {Node* node new Node{value, nullptr};if (tail_ nullptr) {head_ node;tail_ node;} else {tail_-next node;tail_ node;}size_;}bool insert(std::size_t pos, int value) {if (pos size_) return false;if (pos 0) {push_front(value);return true;}if (pos size_) {push_back(value);return true;}Node* prev head_;for (std::size_t i 0; i 1 pos; i) {prev prev-next;}Node* node new Node{value, prev-next};prev-next node;size_;return true;}bool erase(std::size_t pos) {if (pos size_) return false;if (pos 0) {Node* victim head_;head_ head_-next;delete victim;--size_;if (size_ 0) {tail_ nullptr;}return true;}Node* prev head_;for (std::size_t i 0; i 1 pos; i) {prev prev-next;}Node* victim prev-next;prev-next victim-next;if (victim tail_) {tail_ prev;}delete victim;--size_;return true;}int* find(int value) {for (Node* p head_; p ! nullptr; p p-next) {if (p-value value) return p-value;}return nullptr;}const int* find(int value) const {for (const Node* p head_; p ! nullptr; p p-next) {if (p-value value) return p-value;}return nullptr;}void reverse() {Node* prev nullptr;Node* cur head_;tail_ head_;while (cur ! nullptr) {Node* next cur-next;cur-next prev;prev cur;cur next;}head_ prev;}void clear() {Node* p head_;while (p ! nullptr) {Node* next p-next;delete p;p next;}head_ nullptr;tail_ nullptr;size_ 0;}std::size_t size() const { return size_; }bool empty() const { return head_ nullptr; }void print() const {for (const Node* p head_; p ! nullptr; p p-next) {std::cout p-value ;}std::cout \n;}private:struct Node {int value;Node* next;};void swap(SinglyList other) noexcept {std::swap(head_, other.head_);std::swap(tail_, other.tail_);std::swap(size_, other.size_);}Node* head_ nullptr;Node* tail_ nullptr;std::size_t size_ 0;};int main() {SinglyList list;list.push_back(1);list.push_back(2);list.push_back(3);list.push_front(0);list.insert(2, 99);list.erase(1);list.reverse();list.print();SinglyList copy list;copy.push_back(4);copy.print();list.print();return 0;}reverse()中tail_ head_在循环前执行循环后head_指向原来的尾节点tail_指向原来的头节点两个不变量都保持。insert的循环i 1 pos走到pos-1位置pos等于 1 时循环不执行prev就是头节点逻辑正确。常见坑点1. 头插时先改head_再连后继❌head_ node; node-next head_;形成自环并丢失原链表。✅node-next head_; head_ node;。2. 删除尾节点不更新tail_❌ 只改前驱的next并deletetail_仍指向已释放节点。✅if (victim tail_) tail_ prev;。3. 删除唯一节点后tail_悬垂❌ 删头后只更新head_不管tail_。✅size_变为 0 时把tail_置空。4. 析构只删头节点❌delete head_;就结束。✅ 循环保存next再逐个删除。5. 拷贝构造只复制指针❌head_ other.head_;两个链表共享节点。✅ 深拷贝逐个push_back新节点。6. 拷贝赋值不处理自赋值❌ 先clear()再读other当this other时读到已释放内容。✅ 拷贝并交换或先判断this ! other。7. 反转时先改指针再保存后继❌cur-next prev; next cur-next;next拿到的是prev。✅ 先next cur-next;再改cur-next。8. 按位置插入/删除不检查边界❌ 对空表erase(0)直接解引用head_。✅pos size_时返回 false空表不进入删除逻辑。总结操作关键点复杂度头插新节点先连旧头O(1)尾插维护tail_O(1)按位置插入走到前驱先连后断O(n)按位置删除保存待删节点更新tail_O(n)查找遍历比较O(n)反转三指针先存后继O(n)清空/析构逐个保存后继再释放O(n)拷贝深拷贝O(n)单链表的实现可以归结为两条纪律每次修改指针前先保存「会丢失的那一端」每次删除或插入后检查head_、tail_、size_三个不变量。把这两条守住头插、尾插、反转、析构就不会出现「丢链」「悬垂」「重复释放」这三类经典问题。