链表的基本操作（C语言代码）

解题思路:

注意事项:

main函数结束及删除节点时，删除malloc申请的堆空间，避免内存泄漏

参考代码:

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

/** 链表节点 */
typedef struct LNode {
    int val;
    struct LNode *next;
} LNode;

/** 从链表中获取指定位置的节点 */
LNode *getNode(LNode *L, int index) {
    if (index == 0) {
        return L;
    }
    if (index == 1) {
        return L->next;
    }
    LNode *p = L->next;
    while (p && --index) {
        p = p->next;
    }
    return p;
}

/** 从链表中获取指定位置的节点值*/
void get(LNode *L, int index) {
    LNode *p = getNode(L, index);
    if (p) {
        printf("%d\n", p->val);
    } else {
        printf("get fail\n");
    }
}

/** 从链表中删除指定位置的节点 */
void delete(LNode *L, int index) {
    LNode *p = getNode(L, index - 1);   // 获取删除的前一个节点
    if (p && p->next) {
        LNode *node = p->next;
        p->next = p->next->next;
        free(node);     // 释放删除节点的堆空间
        printf("delete OK\n");
    } else {
        printf("delete fail\n");
    }
}

/** 在链表指定位置插入节点 */
void insert(LNode *L, int index, int val) {
    LNode *p = getNode(L, index - 1);   // 获取插入的前一个节点
    if (p) {
        LNode *node = malloc(sizeof(LNode));
        node->val = val;
        node->next = p->next;
        p->next = node;
        printf("insert OK\n");
    } else {
        printf("insert fail\n");
    }
}

/** 打印输出链表 */
void show(const LNode *L) {
    L = L->next;
    if (!L) {
        printf("Link list is empty\n");
        return;
    }
    while (L) {
        printf("%d ", L->val);
        L = L->next;
    }
    printf("\n");
}

/** 创建带头节点的链表*/
LNode *createList(int n) {
    LNode *L = malloc(sizeof(LNode));   // 虚拟头结点
    L->next = NULL;
    LNode *node;
    while (n--) {
        node = malloc(sizeof(LNode));
        scanf("%d", &node->val);
        node->next = L->next;   // 头插法
        L->next = node;
    }
    return L;
}

/** 释放链表节点 */
void freeList(LNode *L) {
    while (L) {
        LNode *node = L;
        L = L->next;
        free(node);
    }
}

int main() {
    int n, m;
    scanf("%d", &n);    // 初始化链表节点数
    LNode *L = createList(n);    // 创建链表
    scanf("%d", &m);    // 操作次数
    char str[10];
    int a, e;
    while (m--) {
        scanf("%s", str);
        switch (str[0]) {
            case 'g':   // get
                scanf("%d", &a);
                get(L, a);
                break;
            case 'i':   // insert
                scanf("%d %d", &a, &e);
                insert(L, a, e);
                break;
            case 'd':   // delete
                scanf("%d", &a);
                delete(L, a);
                break;
            case 's':   // show
                show(L);
                break;
        }
    }
    
    freeList(L);
}