🔥前言
本专栏收录的均为牛客网的算法题目，内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目，也有大厂的面试真题，面试、找工作完全可以来这里找机会。此外，网站内的编码主题多样化，调试功能可运用性强，可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗，快去注册开启算法百炼成神之路吧！
1、AB9【模板】链表
题目链接：点击即可挑战
考查链表的设计，插入，删除操作，做的时候考虑链表尾部的特殊处理，锻炼思维能力
题目描述：
1.1、解题思路
对于模板链表题，只需按照平常学习的知识构建普通单向有头结点的链表即可：
insert和delete方法都需要判断链表中是否有值为x的结点，那么可以单独写一个函数来判断
对于插入和删除操作我都是采用的两个移动指针的方法：ptr在前，pre在后
对于此题来说最后不能输出空格，因此要加条件限制
1.2、代码实现及注释
本题源码：
#include <iostream> using namespace std; struct list { int data; list* next; }; bool judge(list* &L, int x) { list* ptr = L->next; while (ptr) { if (ptr->data == x) return true; else ptr = ptr->next; } return false; } int main() { list* L = (list*)malloc(sizeof(list)); L->next = NULL; int n; cin >> n; for (int i = 0; i < n; i++) { string s; cin >> s; if (s == "insert") { list* ptr = L->next; list* pre = L; int x, y; cin >> x >> y; list* e = (list*)malloc(sizeof(list)); e->next = NULL; e->data = y; if (judge(L, x)) { while (ptr) { if (ptr->data == x) { pre->next = e; e->next = ptr; break; } else { pre = ptr; ptr = ptr->next; } } } else { while (pre->next) { pre = pre->next; } pre->next = e; } } else if (s == "delete") { int x; cin >> x; list* ptr = L->next; list* pre = L; if (judge(L, x)) { while (ptr) { if (ptr->data == x) { if (ptr->next) { pre->next = ptr->next; ptr = NULL; free(ptr); break; } else { pre->next = NULL; ptr = NULL; free(ptr); break; } } else { pre = ptr; ptr = ptr->next; } } } } } list* ptr = L->next; if (ptr == NULL) cout << "NULL"; else { while (ptr) { cout << ptr->data << " "; ptr = ptr->next; } } }
重要注释：
judge函数返回一个布尔类型，为true则链表存在x，为false则不存在x
对于insert操作：
若存在x， 指针pre和ptr逐步遍历，直到ptr指向结点的值为x，将新结点e添加到链表中
若不存在x，让pre指针循环后移到最后一个结点位置，然后将e插入到pre指向的结点后
对于delete操作：
在存在x的情况下，判断其是否在链表的末尾：
若不在链表末尾：让pre指向ptr的下一个结点，删除并释放ptr
若在链表末尾：直接删除并释放ptr指针即可
若不存在x，不进行任何操作
最后就是对链表的内容进行输出：注意输出空格的时候要再链表非末尾的情况下进行
