第1章：线性表之单链表——从节点到逆置，手把手带你吃透

大家好，我是你们的老朋友。今天咱们来聊聊单链表。说实话，链表这东西，我当年学的时候也觉得挺绕的——指针指来指去，一不小心就丢了节点。但等你真正用熟了，你会发现它其实特别灵活，尤其在需要频繁插入删除的场景下，比数组好用太多了。

好，废话不多说，咱们直接开干。

1. 单链表的定义与节点结构

先说说什么是单链表。说白了，单链表就是一组节点串起来的线性结构。每个节点里存两个东西：一个是数据，另一个是指向下一个节点的指针。最后一个节点的指针指向 NULL，表示链表结束了。

我习惯用这样的结构体来定义节点：

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

这里我用了 typedef，这样后面写代码时可以直接用 Node 或 LinkedList，省事不少。你想想看，每次写 struct Node *p 多麻烦，对吧？

2. 头插法与尾插法

创建链表有两种常用方式：头插法和尾插法。这两种方法各有各的适用场景，我分别说说。

头插法

头插法，顾名思义，每次新节点都插在链表头部。这样最后得到的链表顺序和插入顺序是相反的。我早期做项目时，有时候需要逆序输出数据，就会用头插法来建表，一举两得。

void headInsert(LinkedList *L, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *L;   // 新节点指向原来的头节点
    *L = newNode;          // 头指针指向新节点
}

尾插法

尾插法就更好理解了——每次新节点都挂在链表末尾。这样得到的链表顺序和插入顺序一致。我平时写代码，大部分情况都用尾插法，因为更符合直觉。

void tailInsert(LinkedList *L, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*L == NULL) {
        *L = newNode;  // 空链表，新节点就是头节点
        return;
    }

    Node *p = *L;
    while (p->next != NULL) {
        p = p->next;   // 找到最后一个节点
    }
    p->next = newNode;
}

3. 按位查找与按值查找

查找是链表的基本操作。数组查找是 O(1) 的，但链表不行，得从头一个个找。这就是链表的代价——随机访问能力差。

按位查找

按位查找就是找第 i 个节点。注意，链表的下标通常从 1 开始，头节点是第 1 个。

Node* getByIndex(LinkedList L, int i) {
    if (i < 1) return NULL;
    Node *p = L;
    int j = 1;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;  // 如果 i 超出范围，返回 NULL
}

按值查找

按值查找更简单，就是遍历链表，找到第一个数据等于目标值的节点。

Node* getByValue(LinkedList L, int value) {
    Node *p = L;
    while (p != NULL) {
        if (p->data == value) {
            return p;
        }
        p = p->next;
    }
    return NULL;  // 没找到
}

4. 插入与删除节点

插入和删除是链表的强项。数组插入删除要移动大量元素，链表只需要改改指针就行。嗯，这里要注意的是指针修改的顺序——顺序错了，链表就断了。

插入节点

在位置 i 插入一个节点，核心操作是两步：新节点指向第 i 个节点，第 i-1 个节点指向新节点。顺序不能反。

void insertNode(LinkedList *L, int i, int data) {
    if (i < 1) return;

    if (i == 1) {
        headInsert(L, data);  // 插在头部，用头插法
        return;
    }

    Node *prev = getByIndex(*L, i - 1);
    if (prev == NULL) return;  // 位置不合法

    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = prev->next;
    prev->next = newNode;
}

删除节点

删除节点更简单：找到前驱节点，让它的 next 跳过要删除的节点，直接指向下一个。然后 free 掉被删除的节点。

void deleteNode(LinkedList *L, int i) {
    if (i < 1 || *L == NULL) return;

    Node *p;
    if (i == 1) {
        p = *L;
        *L = (*L)->next;  // 头节点后移
        free(p);
        return;
    }

    Node *prev = getByIndex(*L, i - 1);
    if (prev == NULL || prev->next == NULL) return;

    p = prev->next;
    prev->next = p->next;
    free(p);
}

5. 链表的逆置

链表逆置是个经典问题，面试也常考。思路其实不复杂：遍历链表，把每个节点的 next 指针指向前一个节点。我习惯用三个指针来操作：pre、cur、next。

void reverseList(LinkedList *L) {
    Node *pre = NULL;
    Node *cur = *L;
    Node *next = NULL;

    while (cur != NULL) {
        next = cur->next;  // 保存下一个节点
        cur->next = pre;   // 反转指针
        pre = cur;         // pre 前移
        cur = next;        // cur 前移
    }
    *L = pre;  // 最后 pre 指向新头节点
}

为什么会这样？你看，每次循环我们做三件事：先保存下一个节点，然后把当前节点的 next 指向前一个，最后两个指针都往前移。这样一轮下来，链表就反转了。我当年第一次写这个算法时，画了半小时图才搞明白。你们要是觉得晕，也建议画图理解。

知识体系总览

下面这张图是我画的单链表核心知识结构，你们可以对照着复习：

这张图把单链表的几个核心操作都串起来了。从节点定义开始，到两种建表方式，再到查找、插入删除，最后是逆置。你们可以把它当作复习路线图。

好了，单链表的内容就讲到这里。代码不多，但每个操作背后的指针变化一定要想清楚。我建议你们自己动手写一遍，画一画指针的指向变化，比光看代码效果好得多。

---