赞
踩
之前我们对C语言进行了一定的学习,有了一些基础之后,我们就可以学习一些比较基础的数据结构算法题了。这部分的知识对于我们编程的深入学习非常有用,对于一些基本的算法,我们学习之后,就可以参加一些编程比赛了(蓝桥杯)。
学习前提
1.至少掌握一门计算机编程语言。
2.有一定的数学基础和逻辑思考能力。
1.复习好C语言以及C++的基础知识,尤其是指针这一块的知识,当然使用别的计算机编程语言也可以,你完全可以把本教程提供的代码当作伪代码来学习。
2.阅读时建议顺序阅读,多思考理解,不要轻易去大量的复制粘贴代码(虽说这也是一个技巧),代码结合图示的学习方法是相当重要的,弄懂原理才是编写代码的基础。
3.你可以做一些适当的摘抄,虽然有的时候笔记记一次以后不再阅读,但是在写字的时候也是一种加强记忆的过程,笔记的过程就可以加强你的理解。
希望你不负此行。
好了今天带大家刷几道牛客网上的算法题练练手。
这里给大家提供两个思路:
思路一:遍历原链表,遇见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;
- }
876. 链表的中间结点 - 力扣(LeetCode)https://leetcode.cn/problems/middle-of-the-linked-list/description/
思路一:统计链表的节点个数,通过除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;
- }
这样就通过了。
206. 反转链表 - 力扣(LeetCode)https://leetcode.cn/problems/reverse-linked-list/description/
思路一:创建新链表,遍历原链表的节点将其插入到新的链表中。
思路二:创建三个节点,分别记录前驱节点,当前节点,后继节点,改变原链表指针指向
我们这里采用思路二解题:
- 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;
- }
好了,今天就分享这些了,感谢大家观看,有问题,随时评论区提问哦。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。