1 单链表

GESP C++ 五级：单链表精讲

核心目标：理解单链表的逻辑结构与内存模型，掌握节点的定义、创建、遍历、插入、删除、查找、反转等基本操作，能分析操作的时间复杂度，能解决链表模拟类综合问题。
单链表由一个个节点串成，每个节点存数据和指向下一个节点的指针；头指针是入口，尾节点的 next 为 NULL；插入删除改指针，遍历查找顺着 next 走。

一、考纲定位

GESP 五级数据结构部分明确要求掌握线性表，包括顺序表（数组）和链表。其中单链表是链表的基础，考试中常考：

考点	重要程度	考查形式
节点结构体定义	★★★★★	代码填空、选择题
头插法/尾插法建表		编程题
遍历链表		编程题、程序阅读
插入节点	★★★★☆	编程题、代码填空
删除节点		编程题、代码填空
查找节点		编程题
反转链表	★★★☆☆	编程题、选择题
求链表长度	★★★☆☆	编程题
链表与数组对比	★★★★☆	选择题
复杂度分析	★★★★☆	选择题

五级还要求掌握双向链表、循环链表，但单链表是基础，必须优先掌握。

二、单链表基本概念

1. 什么是单链表

单链表是一种链式存储的线性表。每个数据元素称为节点，节点包含两部分：

数据域：存放数据
指针域：存放指向下一个节点的指针

所有节点通过指针依次连接，最后一个节点的指针域为空（NULL 或 nullptr）。

2. 逻辑结构 vs 物理结构

对比项	数组（顺序表）	单链表
存储方式	连续内存	离散内存，靠指针连接
随机访问	支持 O(1)	不支持，必须从头遍历 O(n)
插入/删除	平均 O(n)，需移动元素	O(1)（已知前驱时）
内存分配	静态，需预先确定大小	动态，按需分配
缓存友好	好	差

3. 关键术语

术语	含义
头指针	指向链表第一个节点的指针
头节点	附加在第一个数据节点之前的虚拟节点，不存数据（可选）
首元节点	链表中第一个实际存储数据的节点
尾节点	最后一个节点，其 `next` 为 `NULL`
空链表	头指针为 `NULL`，或只有头节点且 `next` 为 `NULL`

三、节点定义

1. 基本定义

struct Node {
    int data;       // 数据域
    Node *next;     // 指针域，指向下一个节点
};

2. 使用 typedef 简化

typedef struct Node {
    int data;
    struct Node *next;
} Node;

3. 带头节点的定义

实际编程中常用带头节点的链表，头节点不存有效数据，简化插入删除操作。

Node *head = new Node;   // 头节点
head->next = NULL;       // 初始为空链表

四、单链表基本操作

1. 创建链表（尾插法）

尾插法：每次在链表末尾插入新节点，保持节点顺序与输入顺序一致。

Node *createList(int n) {
    Node *head = new Node;   // 头节点
    head->next = NULL;
    Node *tail = head;       // 尾指针

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node *p = new Node;
        p->data = x;
        p->next = NULL;
        tail->next = p;      // 接到尾部
        tail = p;            // 更新尾指针
    }
    return head;
}

2. 头插法

头插法：每次在头节点之后插入新节点，节点顺序与输入顺序相反。

Node *createListHead(int n) {
    Node *head = new Node;
    head->next = NULL;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node *p = new Node;
        p->data = x;
        p->next = head->next;   // 新节点指向原首元节点
        head->next = p;         // 头节点指向新节点
    }
    return head;
}

3. 遍历链表

void printList(Node *head) {
    Node *p = head->next;   // 带头节点，从首元节点开始
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

4. 求链表长度

int getLength(Node *head) {
    int len = 0;
    Node *p = head->next;
    while (p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}

5. 查找节点

查找第一个值为 x 的节点，返回其指针；找不到返回 NULL。

Node *find(Node *head, int x) {
    Node *p = head->next;
    while (p != NULL) {
        if (p->data == x) return p;
        p = p->next;
    }
    return NULL;
}

6. 插入节点

在指定节点后插入

void insertAfter(Node *p, int x) {
    Node *newNode = new Node;
    newNode->data = x;
    newNode->next = p->next;
    p->next = newNode;
}

在链表头部插入（头节点之后）

void insertHead(Node *head, int x) {
    Node *newNode = new Node;
    newNode->data = x;
    newNode->next = head->next;
    head->next = newNode;
}

在链表尾部插入

void insertTail(Node *head, int x) {
    Node *newNode = new Node;
    newNode->data = x;
    newNode->next = NULL;

    Node *p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
}

7. 删除节点

删除指定值后的第一个节点

void deleteNode(Node *head, int x) {
    Node *p = head;
    while (p->next != NULL) {
        if (p->next->data == x) {
            Node *q = p->next;
            p->next = q->next;
            delete q;          // 释放内存
            return;
        }
        p = p->next;
    }
}

删除指定节点（已知前驱）

void deleteAfter(Node *p) {
    if (p->next == NULL) return;
    Node *q = p->next;
    p->next = q->next;
    delete q;
}

8. 反转链表

反转单链表是五级高频考点，有两种常用方法。

方法一：迭代法（推荐）

Node *reverseList(Node *head) {
    Node *prev = NULL;
    Node *curr = head->next;   // 带头节点，从首元节点开始
    while (curr != NULL) {
        Node *nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    head->next = prev;   // 头节点指向新的首元节点
    return head;
}

方法二：头插法

Node *reverseList2(Node *head) {
    Node *newHead = new Node;
    newHead->next = NULL;
    Node *p = head->next;
    while (p != NULL) {
        Node *q = p->next;
        p->next = newHead->next;
        newHead->next = p;
        p = q;
    }
    return newHead;
}

9. 清空链表 / 释放内存

void clearList(Node *head) {
    Node *p = head->next;
    while (p != NULL) {
        Node *q = p->next;
        delete p;
        p = q;
    }
    head->next = NULL;
}

五、复杂度分析

操作	时间复杂度	说明
遍历	O(n)	从头到尾
求长度		需遍历
按值查找
按位查找
头部插入	O(1)	头节点后插入
尾部插入	O(n)	需找到尾节点（若有尾指针则 O(1)）
删除已知前驱的节点	O(1)	改指针
删除指定值节点	O(n)	需先查找
反转		遍历一次
空间复杂度		存储 n 个节点

六、单链表与数组对比（高频选择题）

对比项	数组	单链表
存储	连续	离散
随机访问	O(1)	O(n)
插入/删除	O(n)	O(1)（已知位置）
内存分配	静态	动态
空间开销	小	需额外指针域
缓存命中	高	低
适用场景	频繁随机访问	频繁插入删除

七、GESP 五级单链表真题示例

真题1：链表节点定义（选择题）

以下哪个选项正确定义了一个单链表节点结构体？
A. struct Node { int data; Node next; };
B. struct Node { int data; Node *next; };
C. struct Node { int data; *Node next; };
D. struct Node { int data; struct next; };
答案：B
A 错：Node next 会导致结构体无限递归定义。
C 错：*Node next 语法错误。
D 错：struct next 不是合法的节点指针类型。

真题2：尾插法建表（代码填空）

下面是用尾插法创建链表的代码，横线处应填入（）。
Node *createList(int n) {
 Node *head = new Node;
 head->next = NULL;
 Node *tail = head;
 for (int i = 0; i < n; i++) {
     int x;
     cin >> x;
     Node *p = new Node;
     p->data = x;
     p->next = NULL;
     ______;
     tail = p;
 }
 return head;
}
A. tail->next = p;
B. p->next = tail;
C. head->next = p;
D. p->next = head;
答案：A

代码分析：

  Node *createList(int n) {
   Node *head = new Node;   // 创建头结点/哨兵结点，不存有效数据
   head->next = NULL;       // 初始为空链表
   Node *tail = head;       // tail 始终指向当前尾结点

   for (int i = 0; i < n; i++) {
       int x;
       cin >> x;

       Node *p = new Node;  // 创建新节点
       p->data = x;         // 填入数据
       p->next = NULL;      // 新节点将作为新的尾结点

       tail->next = p;      // 【填空】A：把新节点接到当前尾结点后面
       tail = p;            // 更新尾指针，使其指向新的尾结点
   }

   return head;             // 返回带头结点的链表
}

真题3：链表反转（程序阅读）

以下代码实现链表反转，输出结果是（）。

// 链表为 1 -> 2 -> 3 -> 4
Node *reverse(Node *head) {
 Node *prev = NULL;
 Node *curr = head;
 while (curr != NULL) {
     Node *nextTemp = curr->next;
     curr->next = prev;
     prev = curr;
     curr = nextTemp;
 }
 return prev;
}

答案：4 -> 3 -> 2 -> 1

代码分析

cpp
Node *reverse(Node *head) {
    Node *prev = NULL;       // prev 指向已经反转部分的头结点，初始为空
    Node *curr = head;       // curr 指向当前待反转节点

    while (curr != NULL) {
        Node *nextTemp = curr->next; // 先保存下一个节点，防止反转后断链
        curr->next = prev;           // 反转指针：当前节点指向前一个节点
        prev = curr;                 // prev 后移，已反转部分扩大
        curr = nextTemp;             // curr 后移，继续处理原链表下一个节点
    }

    return prev;             // 循环结束时，prev 就是反转后的新头结点
}

真题4：删除节点（编程题）

输入 n 个整数构建单链表，再输入一个整数 x，删除链表中第一个值为 x 的节点，输出删除后的链表。

#include<bits/stdc++.h>
using namespace std;

struct Node {
   int data;      // 数据域
   Node *next;    // 指针域
};

int main() {
   int n;
   cin >> n;

   Node *head = new Node;   // 带头结点/哨兵结点，head->next 才是第一个有效数据节点
   head->next = NULL;
   Node *tail = head;       // tail 指向当前尾结点

   // 尾插法构建链表
   for (int i = 0; i < n; i++) {
       int x;
       cin >> x;

       Node *p = new Node;  // 创建新节点
       p->data = x;
       p->next = NULL;

       tail->next = p;      // 将新节点接到尾部
       tail = p;            // 更新尾指针
   }

   int x;
   cin >> x;

   // 删除第一个值为 x 的节点
   Node *p = head;          // 从哨兵头结点开始，便于删除第一个有效数据节点
   while (p->next != NULL) {
       if (p->next->data == x) {
           Node *q = p->next;     // q 指向要删除的节点
           p->next = q->next;     // 跳过 q，让前驱直接指向后继
           delete q;              // 释放被删除节点的内存
           break;                 // 只删除第一个值为 x 的节点
       }
       p = p->next;               // 继续向后查找
   }

   // 输出删除后的链表
   p = head->next;          // 从第一个有效数据节点开始输出
   while (p != NULL) {
       cout << p->data << " ";
       p = p->next;
   }

   return 0;
}

八、易错点汇总

忘记初始化头节点：head = new Node; head->next = NULL;
头插法与尾插法混淆：头插法逆序，尾插法顺序一致。
遍历时忘记移动指针：p = p->next; 不能漏，否则死循环。
删除节点后忘记 delete：造成内存泄漏。
删除节点后忘记更新前驱指针：p->next = q->next;
访问空指针：p->next 前必须确保 p != NULL。
反转链表时指针操作顺序错误：先保存 next，再改 curr->next。
带头节点与不带头节点混用：插入删除操作不同，统一风格。
尾插法没有维护尾指针：每次插入都遍历到尾，效率低。
忘记释放链表内存：虽然考试中不强制，但好习惯。
链表长度计算错误：带头节点时从 head->next 开始计数。
混淆 p->next 和 p：插入删除时注意操作的是前驱节点。

九、速查表

需求	代码片段
节点定义	`struct Node { int data; Node *next; };`
创建头节点	`Node *head = new Node; head->next = NULL;`
尾插法	`tail->next = p; tail = p;`
头插法	`p->next = head->next; head->next = p;`
遍历	`for (Node *p = head->next; p; p = p->next)`
求长度	`int len=0; for (Node *p=head->next; p; p=p->next) len++;`
查找	`for (Node *p=head->next; p; p=p->next) if (p->data==x) return p;`
插入（p后）	`newNode->next = p->next; p->next = newNode;`
删除（p后）	`Node *q = p->next; p->next = q->next; delete q;`
反转（迭代）	见上文代码
清空	遍历 delete，`head->next = NULL;`

十、总结

单链表是 GESP 五级数据结构的基础。

单链表由节点组成，每个节点存数据和指向下一个节点的指针。
头指针是入口，尾节点的 next 为 NULL。
头插法逆序，尾插法顺序，根据题目要求选择。
遍历用 while (p != NULL) { ... p = p->next; }。
插入节点：先连后断，newNode->next = p->next; p->next = newNode;。
删除节点：先保存待删节点，再改前驱指针，最后 delete。
反转链表：用 prev、curr、nextTemp 三指针迭代。
单链表按位查找 O(n)，插入删除 O(1)（已知位置）。
数组随机访问快，链表插入删除快，根据场景选择。
多练“尾插法建表”“删除节点”“反转链表”三类编程题。

复习建议：先把节点定义、尾插法建表、遍历、求长度四个基础操作写熟；再练插入、删除、查找；最后攻克反转链表和综合模拟题。考试中先确定是否带头节点，再理清指针操作顺序，最后逐行检查空指针和内存释放。