单链表结构
在阅读这篇文章之前大家要对于单链表结构做一个详细的了解
关于单链表结构大家可以参考我的这篇文章
这里直接讲解关于单链表的两道题目来加深下同学们对于单链表的理解
翻转单链表
该题目来自lc206题 题目和描述如下
给我们一个单链表的头节点 要求我们翻转整个单链表
解析：
对于这道题来说并没有过多的考查我们的算法能力 它想要考查的应该是我们对于单链表的熟悉程度 以及coding能力
思路也很简单 我们设计三个指针 一个指针指向当前要翻转的节点 一个指针指向当前要翻转节点的前一个节点 一个指针指向要翻转节点的下一个节点
翻转完毕之后两个指针前进一次 直到翻转到单链表末尾为止
代码表示如下
class Solution { public: ListNode* reverseList(ListNode* head) { if (head == nullptr) { return nullptr; } ListNode* prev = nullptr; ListNode* cur = head; ListNode* next = head; while (next) { next = next->next; cur->next = prev; prev = cur; cur = next; } return prev; } };
如果说这道题目有什么需要注意的地方的话就是注意空指针的引用问题
我们要对next指针判定非空之后才能让它指向下一个位置
运行结果如下
删除节点
改题目来自lc的剑指offer18题 题目和描述如下
我们首先要考虑的是要删除的值是否为头节点
- 如果是头节点 我们返回头节点的值就要变化
- 如果不是头节点正常删除即可
由于题目中交代了我们不需要使用freee或者是delete来删除节点 所以说我们直接改变指针指向从而来改变这个单链表的结构就好了
代码表示如下
class Solution { public: ListNode* deleteNode(ListNode* head, int val) { // head -> val == val while (head != nullptr && head->val == val) { head = head->next; } if (head == nullptr) { return nullptr; } ListNode* prev = head; ListNode* cur = head->next; while(cur) { if (cur -> val == val) { prev->next = cur->next; cur = cur->next; } else { prev = cur; cur = cur->next; } } return head; } };
运行结果如下
双链表
关于双链表结构我们可以认为就是单链表结构加上了一个向前指向的指针 这样子在在链表的任意节点就既可以向前又可以向后了
关于双链表结构不熟悉的同学可以参考我的这篇博客
双链表的coding其实和单链表差不多 因为这一片博客是为了让大家了解下基础的数据结构 这里就不过多赘述了
栈和队列
关于栈和队列数据结构不了解的同学可以参考我的这篇博客
简单来说 栈是一个后进先出的数据结构 队列是一个先进先出的数据结构
下面是几道题让大家更了解栈和队列这两种数据结构
用栈实现队列
该题目出自lc232题目 题目和描述如下
题目要求让我们使用两个栈来实现一个队列 该题目博主在自己之前的博客中已经做过详细的讲解了 大家可以跳转到具体的博客学习
用队列实现栈
同样这 这个题目的要求是让我们使用两个队列来实现一个栈 这个题目博主在之前的博客中也讲解过了 大家可以跳转到具体的博客学习
哈希表
在C++中的map有两个 它们的底层分别是红黑树和哈希表
如果我们想要使用红黑树来定义一个map 我们可以这么做
map<T, T> M;
如果我们想要使用哈希表来定义一个map 我们可以这么做
unordered_map<T , T> M;
关于这两个数据结构的具体用法可以参考这两篇博客
