GESP 6级

链表概念

6级 · 指针/STL/复杂度
💡 为什么重要

链表是学习所有高级数据结构（树、图）的基础。与数组相比，链表在插入和删除时不需要移动元素，效率更高。GESP 6级考试常考链表的创建、遍历、插入、删除操作，以及链表与数组的对比分析。理解链表也是理解"指针如何连接数据"的关键。

📖 前置知识
  • 指针基础（指针声明、& 取地址、* 解引用、-> 成员访问）
  • 结构体（struct）的定义和使用
  • new/delete 动态内存分配
  • while 循环
🔍 链表是什么？

想象一列火车：每节车厢装着货物（数据），车厢之间通过挂钩连接（指针）。你不需要所有车厢紧挨着停在站台上，它们可以散落在不同地方，只要挂钩连着就行。

链表由节点（Node）组成，每个节点包含两部分：

  • 数据域：存数据（如一个 int）
  • 指针域：存下一个节点的地址（像火车的挂钩）

最后一个节点的指针域为 nullptr（空），表示链表结束。

📐 链表结构
单链表：
[1|→] → [2|→] → [3|→] → NULL
每个节点：[数据 | 指向下一个的指针]

节点定义：
struct ListNode {
  int val; // 数据
  ListNode* next; // 指向下一个节点
};

数组 vs 链表：
数组：连续内存，按下标O(1)访问，中间插入/删除O(n)
链表：不连续内存，必须从头遍历O(n)访问，中间插入/删除O(1)
💻 代码详解
📝 示例1：链表的创建和遍历
#include <iostream>
using namespace std;

// 定义链表节点
struct ListNode {
    int val;                  // 数据域：存值
    ListNode *next;           // 指针域：指向下一个节点

    // 构造函数：方便创建节点
    ListNode(int x) : val(x), next(nullptr) {
        // val 初始化为 x
        // next 初始化为 nullptr（不指向任何节点）
    }
};

int main() {
    // 手动创建 1 → 2 → 3 → NULL
    ListNode *head = new ListNode(1);  // 创建节点1
    head->next = new ListNode(2);     // 节点1指向节点2
    head->next->next = new ListNode(3); // 节点2指向节点3
    // 此时：1 → 2 → 3 → NULL

    // 遍历链表：从头开始，沿着next一直走到nullptr
    ListNode *cur = head;      // cur 从头开始
    while (cur != nullptr) {   // 当前节点不是空
        cout << cur->val;     // 打印当前节点的值
        if (cur->next != nullptr) {
            cout << " → ";    // 如果后面还有，打印箭头
        }
        cur = cur->next;       // 移动到下一个节点
    }
    cout << " → NULL" << endl;
    // 输出: 1 → 2 → 3 → NULL

    // 释放内存（逐个delete）
    cur = head;
    while (cur != nullptr) {
        ListNode *temp = cur;   // 保存当前节点
        cur = cur->next;       // 先移到下一个
        delete temp;            // 再释放当前节点
    }

    return 0;
}
📝 示例2：头插法和尾插法
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// ★ 头插法：每次在链表头部插入（顺序会反转）
// 插入 1, 2, 3 后链表变成 3 → 2 → 1 → NULL
ListNode* buildByHeadInsert(int arr[], int n) {
    ListNode *head = nullptr;  // 初始为空链表

    for (int i = 0; i < n; i++) {
        ListNode *node = new ListNode(arr[i]);
        // 步骤：
        // 1. 新节点的next指向当前头
        node->next = head;
        // 2. 头指针指向新节点
        head = node;
        // 新节点成为了新的头部
    }
    return head;
}

// ★ 尾插法：每次在链表尾部插入（保持原始顺序）
// 插入 1, 2, 3 后链表变成 1 → 2 → 3 → NULL
ListNode* buildByTailInsert(int arr[], int n) {
    ListNode *head = nullptr;  // 头指针
    ListNode *tail = nullptr;  // 尾指针

    for (int i = 0; i < n; i++) {
        ListNode *node = new ListNode(arr[i]);
        if (head == nullptr) {
            // 链表为空，新节点既是头也是尾
            head = node;
            tail = node;
        } else {
            // 把新节点接到尾部
            tail->next = node;
            // 更新尾指针
            tail = node;
        }
    }
    return head;
}

// 打印链表的辅助函数
void printList(ListNode *head) {
    ListNode *cur = head;
    while (cur != nullptr) {
        cout << cur->val;
        if (cur->next) cout << " → ";
        cur = cur->next;
    }
    cout << " → NULL" << endl;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};

    cout << "头插法: ";
    ListNode *list1 = buildByHeadInsert(arr, 5);
    printList(list1);
    // 输出: 5 → 4 → 3 → 2 → 1 → NULL（反转了！）

    cout << "尾插法: ";
    ListNode *list2 = buildByTailInsert(arr, 5);
    printList(list2);
    // 输出: 1 → 2 → 3 → 4 → 5 → NULL（保持顺序）

    return 0;
}
📝 示例3：链表的插入和删除
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

void printList(ListNode *head) {
    ListNode *cur = head;
    while (cur) {
        cout << cur->val << " → ";
        cur = cur->next;
    }
    cout << "NULL" << endl;
}

// 在节点 prev 后面插入值为 x 的新节点
void insertAfter(ListNode *prev, int x) {
    ListNode *node = new ListNode(x);
    // 步骤1: 新节点的next指向prev的下一个
    node->next = prev->next;
    // 步骤2: prev的next指向新节点
    prev->next = node;
    // 顺序不能反！否则会丢失原后面的节点
}

// 删除节点 prev 后面的那个节点
void deleteAfter(ListNode *prev) {
    if (prev->next == nullptr) return; // 后面没节点，不操作
    ListNode *target = prev->next;      // 要删除的节点
    prev->next = target->next;          // 跳过target
    delete target;                        // 释放target的内存
}

int main() {
    // 创建链表: 1 → 3 → 5 → NULL
    ListNode *head = new ListNode(1);
    head->next = new ListNode(3);
    head->next->next = new ListNode(5);

    cout << "原始: ";
    printList(head);

    // 在1后面插入2: 1 → 2 → 3 → 5
    insertAfter(head, 2);
    cout << "插入2后: ";
    printList(head);

    // 在2后面插入4: 1 → 2 → 4 → 3 → 5
    insertAfter(head->next, 4);
    cout << "插入4后: ";
    printList(head);

    // 删除2后面的4: 1 → 2 → 3 → 5
    deleteAfter(head->next);
    cout << "删除4后: ";
    printList(head);

    return 0;
}
📝 示例4：查找链表长度和搜索
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 求链表长度
int getLength(ListNode *head) {
    int count = 0;                // 计数器
    ListNode *cur = head;         // 从头开始
    while (cur != nullptr) {      // 遍历到末尾
        count++;                  // 每经过一个节点+1
        cur = cur->next;          // 移到下一个
    }
    return count;                 // 返回总数
}

// 在链表中查找值 x，返回节点指针
ListNode* find(ListNode *head, int x) {
    ListNode *cur = head;
    while (cur != nullptr) {
        if (cur->val == x) {
            return cur;           // 找到了，返回节点
        }
        cur = cur->next;          // 没找到，继续
    }
    return nullptr;               // 遍历完都没找到
}

int main() {
    ListNode *head = new ListNode(10);
    head->next = new ListNode(20);
    head->next->next = new ListNode(30);

    cout << "长度: " << getLength(head) << endl;
    // 输出: 长度: 3

    ListNode *found = find(head, 20);
    if (found) {
        cout << "找到了: " << found->val << endl;
        // 输出: 找到了: 20
    } else {
        cout << "没找到" << endl;
    }

    return 0;
}
⚠️ 易错点
  • 插入/删除时顺序搞反：插入新节点时，必须先让新节点指向后面，再让前面指向新节点。否则后面的节点就丢失了
  • 丢失头指针：如果直接把 head 移动了（如 head = head->next;），就找不到链表开头了。需要用临时变量保存
  • 遍历时忘记移动指针：如果 while 循环中没有 cur = cur->next;，会死循环
  • 访问 nullptr 的成员：在 cur == nullptr 时访问 cur->val 会崩溃。每次解引用前检查是否为空
  • 内存泄漏：new 创建的节点如果不 delete，内存永远无法回收。程序结束前应遍历释放
  • 不能用下标访问：链表不像数组，不能用 head[2]，必须从头遍历到第2个
🎯 练习建议
  • 入门：手动创建 3 个节点的链表，用 while 循环遍历并打印
  • 进阶：实现头插法和尾插法，分别构建链表并对比结果
  • 挑战：反转一个链表（1→2→3→NULL 变成 3→2→1→NULL）
  • 综合：合并两个有序链表，结果仍然有序
  • 调试：用纸笔画出每一步操作后链表的状态，这是理解链表最有效的方法
← 上一个：stack 和 queue 📖 返回主目录 下一个：时间复杂度 →