一、单链表的定义与节点结构

链表这东西，说白了就是一组节点串在一起。每个节点里存着数据，还存着下一个节点的地址。我刚开始学的时候，总觉得它比数组麻烦多了——数组多简单啊，下标一取就完事了。但后来做项目才发现，链表的动态特性太香了。

先看节点怎么定义：

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

这里有个细节——struct Node *next 为什么不能写成 Node *next？因为在 typedef 还没执行完的时候，Node 这个别名还不存在。嗯，这个坑我踩过。

你想想看，数组在内存里是连续的一块，而链表的节点可以东一个西一个。每个节点通过指针串起来，就像一串珍珠，线断了就全散了。

二、单链表的创建与遍历

2.1 创建节点

创建节点其实就是动态分配内存。我个人习惯用 malloc，记得检查返回值：

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

2.2 头插法创建链表

头插法，就是每次新节点都插在头部。这样创建出来的链表，顺序和输入顺序是反的：

Node* createListByHead(int arr[], int n) {
    Node* head = NULL;
    for (int i = 0; i < n; i++) {
        Node* newNode = createNode(arr[i]);
        newNode->next = head;
        head = newNode;
    }
    return head;
}

2.3 尾插法创建链表

尾插法更符合直觉——新节点加在末尾，顺序和输入一致。但需要维护一个尾指针：

Node* createListByTail(int arr[], int n) {
    Node* head = NULL;
    Node* tail = NULL;
    for (int i = 0; i < n; i++) {
        Node* newNode = createNode(arr[i]);
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

2.4 遍历链表

遍历说白了就是从头走到尾，每到一个节点就干点事：

void traverseList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

三、单链表的插入与删除

3.1 插入操作

插入分三种情况：头部插入、中间插入、尾部插入。核心思路就两步——先找到位置，再改指针。

// 在第 pos 个位置插入（从1开始计数）
int insertNode(Node** head, int pos, int data) {
    Node* newNode = createNode(data);
    if (newNode == NULL) return -1;

    if (pos == 1) {
        newNode->next = *head;
        *head = newNode;
        return 0;
    }

    Node* prev = *head;
    for (int i = 1; i < pos - 1 && prev != NULL; i++) {
        prev = prev->next;
    }

    if (prev == NULL) {
        printf("位置无效\n");
        free(newNode);
        return -1;
    }

    newNode->next = prev->next;
    prev->next = newNode;
    return 0;
}

3.2 删除操作

删除比插入简单点，找到目标节点的前驱，跳过它就行了：

int deleteNode(Node** head, int pos) {
    if (*head == NULL) return -1;

    Node* temp;
    if (pos == 1) {
        temp = *head;
        *head = (*head)->next;
        free(temp);
        return 0;
    }

    Node* prev = *head;
    for (int i = 1; i < pos - 1 && prev != NULL; i++) {
        prev = prev->next;
    }

    if (prev == NULL || prev->next == NULL) {
        printf("位置无效\n");
        return -1;
    }

    temp = prev->next;
    prev->next = temp->next;
    free(temp);
    return 0;
}

四、单链表的反转

反转链表是面试高频题，也是很多人的噩梦。其实核心就三句话：记住下一个、指向前一个、往前走。

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;

    while (current != NULL) {
        next = current->next;   // 1. 记住下一个
        current->next = prev;   // 2. 指向前一个
        prev = current;         // 3. prev 往前走
        current = next;         // 4. current 往前走
    }
    return prev;  // prev 就是新头
}

为什么会这样？你想想看，反转的本质就是把每个节点的 next 指向它的前驱。原来指向后面的，现在指向前面的。头变成尾，尾变成头。

知识体系总览

下面这张图把单链表的操作串起来了，你可以对照着看：

单链表的核心操作就这些。说白了，链表操作就是玩指针——指来指去，别指丢了就行。刚开始可能会觉得绕，多画图、多写代码，慢慢就熟了。