单向链表操作的实现（验证性实验） 问题描述 (1) 用头插法（或尾插法）建立带头结点的单向链表。 (2) 对已建立的单向链表实现插入、删除、查找等基本操作

好的，下面是单向链表的基本操作的实现代码（使用头插法建立链表）：

#include <iostream>
using namespace std;

// 定义链表结点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 头插法建立链表
ListNode* createList() {
    ListNode* head = new ListNode(0);  // 创建头结点
    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        ListNode* newNode = new ListNode(x);
        newNode->next = head->next;
        head->next = newNode;
    }
    return head;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* p = head->next;  // 从首结点开始遍历
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

// 插入结点
void insertNode(ListNode* head, int pos, int val) {
    ListNode* p = head;
    for (int i = 0; i < pos && p != NULL; i++) {
        p = p->next;
    }
    if (p == NULL) {
        cout << "插入位置不合法！" << endl;
        return;
    }
    ListNode* newNode = new ListNode(val);
    newNode->next = p->next;
    p->next = newNode;
}

// 删除结点
void deleteNode(ListNode* head, int pos) {
    ListNode* p = head;
    for (int i = 0; i < pos && p != NULL; i++) {
        p = p->next;
    }
    if (p == NULL || p->next == NULL) {
        cout << "删除位置不合法！" << endl;
        return;
    }
    ListNode* delNode = p->next;
    p->next = delNode->next;
    delete delNode;
}

// 查找结点
ListNode* findNode(ListNode* head, int val) {
    ListNode* p = head->next;
    while (p != NULL && p->val != val) {
        p = p->next;
    }
    return p;
}

int main() {
    ListNode* head = createList();
    printList(head);

    int pos, val;
    cout << "请输入插入位置和插入值：";
    cin >> pos >> val;
    insertNode(head, pos, val);
    printList(head);

    cout << "请输入删除位置：";
    cin >> pos;
    deleteNode(head, pos);
    printList(head);

    cout << "请输入查找值：";
    cin >> val;
    ListNode* res = findNode(head, val);
    if (res == NULL) {
        cout << "未找到该结点！" << endl;
    } else {
        cout << "找到结点，它的值为：" << res->val << endl;
    }

    return 0;
}

上述代码中，我们使用了头插法建立链表，也就是说，新插入的结点总是成为链表的首结点。这样做的好处是，链表的插入和删除操作可以在常数时间内完成，但是查找操作的时间复杂度为 O(n)（n 为链表长度）。

我们还实现了插入结点、删除结点和查找结点的操作。其中，插入和删除操作都需要指定插入或删除的位置，而查找操作需要指定要查找的值。如果找到了该结点，就返回它的指针；否则返回 NULL。