单链表： ①建立一个包括头结点和3个结点的（4，2，1)的单链表，实现单链表建立的基本操作。 ②在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。 ③在一个包括头结点和4个结点的（4，3，2，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。

①单链表的建立基本操作：

#include<iostream>
using namespace std;

//定义单链表结点结构体
struct ListNode{
    int val; //结点的值
    ListNode *next; //指向下一个结点的指针
    ListNode(int x) : val(x), next(NULL) {} //结构体构造函数
};

//创建单链表
ListNode* createLinkedList(int arr[], int n){
    ListNode *head = new ListNode(-1); //头结点
    ListNode *cur = head; //指向当前结点的指针
    for(int i=0; i<n; i++){
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return head;
}

//输出单链表
void printLinkedList(ListNode *head){
    ListNode *cur = head->next; //从第一个结点开始输出
    while(cur != NULL){
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

int main(){
    int arr1[] = {4, 2, 1};
    int n1 = sizeof(arr1) / sizeof(int);
    ListNode *head1 = createLinkedList(arr1, n1);
    printLinkedList(head1);

    int arr2[] = {4, 3, 2, 1};
    int n2 = sizeof(arr2) / sizeof(int);
    ListNode *head2 = createLinkedList(arr2, n2);
    printLinkedList(head2);

    return 0;
}

输出结果：

4 2 1 
4 3 2 1 

②单链表的插入基本操作：

//在指定位置插入结点
void insertNode(ListNode *head, int pos, int val){
    ListNode *pre = head; //指向插入位置前一个结点的指针
    for(int i=0; i<pos-1; i++){
        pre = pre->next;
    }
    ListNode *newNode = new ListNode(val); //待插入结点
    newNode->next = pre->next;
    pre->next = newNode;
}

int main(){
    int arr1[] = {4, 2, 1};
    int n1 = sizeof(arr1) / sizeof(int);
    ListNode *head1 = createLinkedList(arr1, n1);
    printLinkedList(head1);
    insertNode(head1, 2, 3);
    printLinkedList(head1);

    int arr2[] = {4, 3, 2, 1};
    int n2 = sizeof(arr2) / sizeof(int);
    ListNode *head2 = createLinkedList(arr2, n2);
    printLinkedList(head2);
    insertNode(head2, 3, 5);
    printLinkedList(head2);

    return 0;
}

输出结果：

4 2 1 
4 3 2 1 
4 3 2 1 
4 3 5 2 1 

③单链表的删除基本操作：

//在指定位置删除结点
void deleteNode(ListNode *head, int pos){
    ListNode *pre = head; //指向删除位置前一个结点的指针
    for(int i=0; i<pos-1; i++){
        pre = pre->next;
    }
    ListNode *delNode = pre->next; //待删除结点
    pre->next = delNode->next;
    delete delNode;
}

int main(){
    int arr1[] = {4, 2, 1};
    int n1 = sizeof(arr1) / sizeof(int);
    ListNode *head1 = createLinkedList(arr1, n1);
    printLinkedList(head1);
    insertNode(head1, 2, 3);
    printLinkedList(head1);
    deleteNode(head1, 2);
    printLinkedList(head1);

    int arr2[] = {4, 3, 2, 1};
    int n2 = sizeof(arr2) / sizeof(int);
    ListNode *head2 = createLinkedList(arr2, n2);
    printLinkedList(head2);
    insertNode(head2, 3, 5);
    printLinkedList(head2);
    deleteNode(head2, 2);
    printLinkedList(head2);

    return 0;
}

输出结果：

4 2 1 
4 3 2 1 
4 2 1 
4 3 2 1 
4 3 5 2 1 
4 5 2 1