题解 | #【模板】链表#

#include <cstring>
#include <iostream>
using namespace std;

// 链表结构
typedef struct LNode {
    int data;
    struct LNode* next;
} LNode, *LinkedList;

// 链表初始化 带头结点的单链表
bool initList(LinkedList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    L -> next = NULL;
    L -> data = -1;
    if (L == NULL) return false;
    return true;
}

// 在当前结点之后插入新结点
bool insertNextNode(LNode* q, int b) {
    if (q == NULL) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s -> data = b;
    s -> next = q -> next;
    q -> next = s;
    return true;
}

// 链表插入
bool insert(LinkedList& L, int a, int b) {
    LNode* p = L;
    // 找到插入值结点的前一个结点
    while (p -> next != NULL && p -> next -> data != a) {
        p = p->next;
    }
    insertNextNode(p, b);
    return true;
}

// 链表删除
bool deleteNode(LinkedList& L, int a) {
    LNode* p = L;
    LNode* q = L;
    while (p != NULL && p -> data != a) {
        q = p;
        p = p -> next;
    }
    if (p == NULL) return true;
    q -> next = p -> next;
    free(p);
    return true;
}

// 打印当前链表的所有data
void printfAllNode(LinkedList L) {
    LNode* p = L;
    if (L -> next == NULL)
        cout << "NULL";
    while (p -> next != NULL) {
        p = p -> next;
        cout << p -> data << " ";
    }
}

int main() {
    int a, b;
    int count = 0;
    string str;
    string inserta = "insert";
    string deletea = "delete";
    cin >> count;
    LinkedList L;
    initList(L);
    for (int i = 0; i < count; i++) {
        // cin >> str >> a >> b;
	    // 注意输入情况 delete 和 insert 结构不同
        cin >> str;
        if(inserta ==  str) {
            cin >> a;
            cin >> b;
        } else {
            cin >> a;
        }
        if (inserta ==  str) {
            insert(L, a, b);
        } else if (deletea ==  str) {
            deleteNode(L, a);
        }
    }
    printfAllNode(L);
    return 0;
}