题目链接：链表的基础操作III
题目描述
请编写一个程序，实现以下链表操作：构建一个单向链表，链表中包含一组整数数据。
1. 实现在链表的第 n 个位置插入一个元素，输出整个链表的所有元素。
2. 实现删除链表的第 m 个位置的元素，输出整个链表的所有元素。
要求：
1. 使用自定义的链表数据结构。
2. 提供一个 linkedList 类来管理链表，包含构建链表、插入元素、删除元素和输出链表元素的方法。
3. 在 main 函数中，创建一个包含一组整数数据的链表，然后根据输入的 n 和 m，调用链表的方法插入和删除元素，并输出整个链表的所有元素。
输入描述
每次输出只有一组测试数据。
每组的第一行包含一个整数 k，表示需要构建的链表的长度。
第二行包含 k 个整数，表示链表中的元素。
第三行包含一个整数 S，表示后续会有 S 行输入，每行两个整数，第一个整数为 n，第二个整数为 x ，代表在链表的第 n 个位置插入 x。
S 行输入...
在 S 行输入后，后续会输入一个整数 L，表示后续会有 L 行输入，每行一个整数 m，代表删除链表中的第 m 个元素。
L 行输入...
输出描述
包含多组输出。
每组第一行输出构建的链表，链表元素中用空格隔开，最后一个元素后没有空格。
然后是 S 行输出，每次插入一个元素之后都将链表输出一次，元素之间用空格隔开，最后一个元素后没有空格；
如果插入位置不合法，则输出“Insertion position is invalid.”。
然后是 L 行输出，每次删除一个元素之后都将链表输出一次，元素之间用空格隔开，最后一个元素后没有空格；如果删除元素后链表的长度为0，则不打印链表。
如果删除位置不合法，则输出“Deletion position is invalid.”。
如果链表已经为空，执行删除操作时不需要打印任何数据。
输入示例
5
1 2 3 4 5
3
4 3
3 4
9 8
2
1
0
输出示例
1 2 3 3 4 5
1 2 4 3 3 4 5
Insertion position is invalid.
2 4 3 3 4 5
Deletion position is invalid.
提示信息
链表为空的时候，不打印
点击查看代码
#include<iostream>
using namespace std;struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};void printLinklist(ListNode* dummyHead){
ListNode* cur = dummyHead;
while(cur -> next != nullptr && cur -> next -> next != nullptr){ //遍历到链表倒数第二个节点cout << cur -> next -> val << ' ';// 输出当前cur的下一个节点值,并加空格,所以实际只有最后一个没打印cur = cur -> next;
}
cout << cur -> next -> val<< endl;//输出最后一个节点值}int main() {int k,val;
cin >> k;
int listLen = k;//记录链表长度，用来控制非法输入输出ListNode* dummyHead = new ListNode(0);//设置虚拟头指针
ListNode* cur = dummyHead;for(int i = 0;i < k;i++){//初始化链表cin >> val;ListNode* newNode = new ListNode(val);cur -> next = newNode;cur = cur -> next;
}int s,n,x;
cin >> s;
for(int i = 0;i < s;i++){cin >> n >> x;if(n <= 0 || n > listLen){//判断插入位置是否合法cout << "Insertion position is invalid." << endl;continue;}cur = dummyHead;//找到插入的前一位置for(int i = 1;i < n;i++){cur = cur -> next;}ListNode* newNode = new ListNode(x);//将新节点插入ListNode* tmp = cur -> next;cur -> next = newNode;cur -> next -> next = tmp;listLen++; //链表长度加1printLinklist(dummyHead);
}int l,m;cin >> l;while(l--){cin >> m;if( m<=0 || m > listLen){ //判断删除位置是否合法cout << "Deletion position is invalid." << endl;continue;}cur = dummyHead; //找到删除前一位置for (int i = 1;i < m;i++) cur = cur -> next;cur -> next = cur -> next -> next;//删除listLen--; //链表长度减1if(listLen != 0) printLinklist(dummyHead);//判断链表是否为空}
return 0;
}
小结
先构建链表结构体
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};
建立链表长度变量，避免插入删除位置不合法，以及记录链表是否为空
int listLen = k;//记录链表长度，用来控制非法输入输出
再对链表初始化
ListNode* dummyHead = new ListNode(0);//设置虚拟头指针ListNode* cur = dummyHead;for(int i = 0;i < k;i++){//初始化链表cin >> val;ListNode* newNode = new ListNode(val);cur -> next = newNode;cur = cur -> next;}
进行插入操作
先判断插入位置是否合法if(n <= 0 || n > listLen){//判断插入位置是否合法cout << "Insertion position is invalid." << endl;continue;}再找插入位置cur = dummyHead;//找到插入的前一位置for(int i = 1;i < n;i++){cur = cur -> next;}进行插入ListNode* newNode = new ListNode(x);//将新节点插入ListNode* tmp = cur -> next;cur -> next = newNode;cur -> next -> next = tmp;最后将链表长度加一listLen++; //链表长度加1打印printLinklist(dummyHead);
删除操作
判断删除位置是否合法if( m<=0 || m > listLen){ //判断删除位置是否合法cout << "Deletion position is invalid." << endl;continue;}找到删除位置cur = dummyHead; //找到删除前一位置
for (int i = 1;i < m;i++) cur = cur -> next;删除cur -> next = cur -> next -> next;//删除链表长度减一listLen--; //链表长度减1先判断是否为空，再打印if(listLen != 0) printLinklist(dummyHead);//判断链表是否为空