之前我们对C语言进行了一定的学习,有了一些基础之后,我们就可以学习一些比较基础的数据结构算法题了。这部分的知识对于我们编程的深入学习非常有用,对于一些基本的算法,我们学习之后,就可以参加一些编程比赛了(蓝桥杯)。
学习前提
1.至少掌握一门计算机编程语言。
2.有一定的数学基础和逻辑思考能力。
如好学好数据结构
1.复习好C语言以及C++的基础知识,尤其是指针这一块的知识,当然使用别的计算机编程语言也可以,你完全可以把本教程提供的代码当作伪代码来学习。
2.阅读时建议顺序阅读,多思考理解,不要轻易去大量的复制粘贴代码(虽说这也是一个技巧),代码结合图示的学习方法是相当重要的,弄懂原理才是编写代码的基础。
3.你可以做一些适当的摘抄,虽然有的时候笔记记一次以后不再阅读,但是在写字的时候也是一种加强记忆的过程,笔记的过程就可以加强你的理解。
希望你不负此行。
好了今天带大家刷几道牛客网上的算法题练练手。
单链表相关经典算法OJ题1: 203. 移除链表元素 – 力扣(LeetCode) https://leetcode.cn/problems/remove-linked-list-elements/description/
这里给大家提供两个思路:
思路一:遍历原链表,遇见val就删除val节点的操作。
思路二:创建一个新链表,遍历原链表,找不为val的节点,尾插到新链表中。
由于第一个思路,改变指针指向,非常麻烦,我们选用思路二解决问题。
1.首先newnode和newtail都指向头节点
2. 利用pcur遍历原链表,若节点的值不为val,则尾差到新链表中,newtail往后走一格,如果值为val则不进行尾插。遍历结束应为:
返回newhead即可得到新的链表。
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode*newhead,*newtail;
newhead=newtail=NULL;
ListNode*pcur=head;
while(pcur)
{
//判断是否为val
if(pcur->val!=val)
{
if(newhead==NULL)
{
newhead=newtail=pcur;
}
else{
newtail->next=pcur;
newtail=newtail->next;
}
}
pcur=pcur->next;
}
if(newtail)
{
newtail->next=NULL;
}
return newhead;
}
单链表相关经典算法OJ题2:
876. 链表的中间结点 – 力扣(LeetCode)
思路一:统计链表的节点个数,通过除2得到中间节点。
思路二:快慢指针,慢指针每次走一步,快指针每次走两步,当快指针走到尾节点时,慢指针刚走到中间节点。
快慢指针是一个比较重要的算法技巧,我们应当熟悉掌握这个算法的技巧。
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode *slow,*fast;
slow=fast=head;
while(fast&&fast->next)
{
slow=slow->next;//
fast=fast->next->next;//
}
return slow;
}
这样就通过了。
单链表相关经典算法OJ题3:
206. 反转链表 – 力扣(LeetCode)
思路一:创建新链表,遍历原链表的节点将其插入到新的链表中。
思路二:创建三个节点,分别记录前驱节点,当前节点,后继节点,改变原链表指针指向
我们这里采用思路二解题:
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
if(head==NULL)
{
return head;
}
//创建三个节点
ListNode* n1,*n2,*n3;
n1=NULL,n2=head,n3=head->next;
//遍历原链表,修改指针的指向
ListNode*pcur=head;
while(n2)
{
//修改n2的指向
n2->next=n1;
//修改三个指针的位置
n1=n2;
n2=n3;
if(n3)
{
n3=n3->next;
}
}
return n1;
}
好了,今天就分享这些了,感谢大家观看,有问题,随时评论区提问哦。
版权声明:本文为博主作者:努力学编程’原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/2301_76249062/article/details/136081744