【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点
✅作者简介:热爱后端语言的大学生,CSDN内容合伙人
✨精品专栏:C++面向对象
🔥系列专栏:算法百炼成神
文章目录
- 🔥前言
- 1、AB9【模板】链表
-
- 1.1、解题思路
- 1.2、代码实现及注释
- 2、AB10 ~ AB11题解
-
- 2.1、解题思路
- 2.2、代码实现及注释
- 3、AB12 删除链表的节点
-
- 3.1、解题思路
- 3.2、代码实现
🔥前言
本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面试真题,面试、找工作完全可以来这里找机会。此外,网站内的编码主题多样化,调试功能可运用性强,可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗,快去注册开启算法百炼成神之路吧!
1、AB9【模板】链表
题目链接:点击即可挑战
考查链表的设计,插入,删除操作,做的时候考虑链表尾部的特殊处理,锻炼思维能力
题目描述:
1.1、解题思路
对于模板链表题,只需按照平常学习的知识构建普通单向有头结点的链表即可:
insert
和delete
方法都需要判断链表中是否有值为x
的结点,那么可以单独写一个函数来判断- 对于插入和删除操作我都是采用的两个移动指针的方法:
ptr
在前,pre
在后 - 对于此题来说最后不能输出空格,因此要加条件限制
1.2、代码实现及注释
本题源码:
#include 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
,不进行任何操作
- 在存在
- 最后就是对链表的内容进行输出:注意输出空格的时候要再链表非末尾的情况下进行
2、AB10 ~ AB11题解
题目链接:合并两个排序链表
2.1、解题思路
- 新创建一个链表,根据已知的两个递增链表的元素大小来升序的在新链表中存储数据
- 头插法建表,使用另外的链表指针作为辅助
- 当两个已知链表有一个已经遍历完时,直接让辅助指针指向非空的链表结点即可
2.2、代码实现及注释
本题源码:
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* vhead = new ListNode(-1); ListNode* cur = vhead; while (pHead1 && pHead2) { if (pHead1->val <= pHead2->val) { cur->next = pHead1; pHead1 = pHead1->next; } else { cur->next = pHead2; pHead2 = pHead2->next; } cur = cur->next; } cur->next = pHead1 ? pHead1 : pHead2; return vhead->next; }};
重要注释:
new ListNode(-1)
相当于创建了一个头结点,cur
作为头插的赋值指针while
循环内部为头插法建立升序链表的过程- 三目运算符目的是让新链表的尾指向剩余链表的头
- 最后返回的时候不需要头结点,因此结果为
vhead->next
反转链表解析的博文地址:反转链表及进阶
反转链表的题目中我用了vector容器自带的reverse
方法,非常适合入门新手
3、AB12 删除链表的节点
题目链接:删除链表节点
3.1、解题思路
观察链表的定义代码可知,该题链表是没有头结点的,那么就可以分情况讨论:
- 若链表第一个结点的值为目标值,直接返回结点的下一个指向即可
- 若链表首结点不是目标值,将其当作头结点即可,使用两个移动指针的方法:
- 步骤与本文上面 模板链表 步骤几乎一致,不做赘述
3.2、代码实现
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param val int整型 * @return ListNode类 */ ListNode* deleteNode(ListNode* head, int val) { ListNode* ptr = head->next; if(head->val==val) return ptr; ListNode* pre = head; while (ptr) { if (ptr->val == val) { if (ptr->next) { pre->next = ptr->next; break; } else { pre->next = NULL; } } else { pre = ptr; ptr = ptr->next; } } return head; }};
链表题打牢基础的话,对后续数据结构的理解也有很大帮助,建议大家多多练习,题目旁的链接点进去即可挑战!