2. 单链表的插入、删除与反转

单链表操作的核心：指针重连与边界处理

单链表由一组离散节点组成，每个节点包含数据域和指向后继的指针域。头插、尾插、按值删除和原地反转这四类操作，本质上都是对 next 指针的重新连接。理解指针的“先保存、后改向”顺序，是避免指针丢失的关键。

节点定义与头插、尾插实现

先定义链表节点结构，再分别实现头插和尾插。头插的时间复杂度为 O(1)，尾插若维护尾指针也为 O(1)，否则需要 O(n) 遍历。

#include <stdio.h>
#include <stdlib.h>

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

/* 创建新节点 */
Node* createNode(int value) {
    Node *node = (Node*)malloc(sizeof(Node));
    if (!node) return NULL;
    node->data = value;
    node->next = NULL;
    return node;
}

/* 头插：新节点成为新的头节点 */
Node* insertHead(Node *head, int value) {
    Node *newNode = createNode(value);
    if (!newNode) return head;
    newNode->next = head;   /* 先让新节点指向原头 */
    return newNode;          /* 再更新头指针 */
}

/* 尾插：遍历到尾部后挂接 */
Node* insertTail(Node *head, int value) {
    Node *newNode = createNode(value);
    if (!newNode) return head;
    if (head == NULL) return newNode;  /* 空链表边界 */
    Node *cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
    return head;
}

按值删除与原地反转

按值删除需要同时维护前驱指针 prev 和当前指针 curr。原地反转则通过三个指针 prev、curr、next 逐步将每个节点的 next 反向。

/* 按值删除第一个匹配节点 */
Node* deleteByValue(Node *head, int value) {
    if (head == NULL) return NULL;  /* 空链表边界 */

    /* 删除头节点的情况 */
    if (head->data == value) {
        Node *temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    Node *prev = head;
    Node *curr = head->next;
    while (curr != NULL) {
        if (curr->data == value) {
            prev->next = curr->next;  /* 跳过 curr */
            free(curr);
            return head;
        }
        prev = curr;
        curr = curr->next;
    }
    return head;  /* 未找到，原样返回 */
}

/* 原地反转：三指针迭代 */
Node* reverseList(Node *head) {
    Node *prev = NULL;
    Node *curr = head;
    while (curr != NULL) {
        Node *next = curr->next;  /* 先保存后继 */
        curr->next = prev;         /* 反转指针方向 */
        prev = curr;               /* prev 前移 */
        curr = next;               /* curr 前移 */
    }
    return prev;  /* prev 最终指向新头 */
}

完整测试与验证

下面用一个 main 函数串联四类操作，并打印每一步的链表状态，便于观察指针变化和边界处理是否正确。

/* 打印链表 */
void printList(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

/* 释放整条链表 */
void freeList(Node *head) {
    while (head != NULL) {
        Node *temp = head;
        head = head->next;
        free(temp);
    }
}

int main(void) {
    Node *head = NULL;

    /* 尾插构建 1 -> 2 -> 3 */
    head = insertTail(head, 1);
    head = insertTail(head, 2);
    head = insertTail(head, 3);
    printf("尾插后: ");
    printList(head);  /* 1 -> 2 -> 3 -> NULL */

    /* 头插 0 */
    head = insertHead(head, 0);
    printf("头插后: ");
    printList(head);  /* 0 -> 1 -> 2 -> 3 -> NULL */

    /* 删除值 2 */
    head = deleteByValue(head, 2);
    printf("删除2后: ");
    printList(head);  /* 0 -> 1 -> 3 -> NULL */

    /* 删除头节点 0 */
    head = deleteByValue(head, 0);
    printf("删除0后: ");
    printList(head);  /* 1 -> 3 -> NULL */

    /* 原地反转 */
    head = reverseList(head);
    printf("反转后: ");
    printList(head);  /* 3 -> 1 -> NULL */

    /* 边界：空链表反转 */
    head = reverseList(NULL);
    printf("空链表反转: ");
    printList(head);  /* NULL */

    freeList(head);
    return 0;
}

关键验证点