当前位置:   article > 正文

数据结构与算法-链表(力扣附链接)

数据结构与算法-链表(力扣附链接)

      之前我们对C语言进行了一定的学习,有了一些基础之后,我们就可以学习一些比较基础的数据结构算法题了。这部分的知识对于我们编程的深入学习非常有用,对于一些基本的算法,我们学习之后,就可以参加一些编程比赛了(蓝桥杯)。

 

 学习前提

  1.至少掌握一门计算机编程语言。

  2.有一定的数学基础和逻辑思考能力。

如好学好数据结构

 1.复习好C语言以及C++的基础知识,尤其是指针这一块的知识,当然使用别的计算机编程语言也可以,你完全可以把本教程提供的代码当作伪代码来学习。

  2.阅读时建议顺序阅读,多思考理解,不要轻易去大量的复制粘贴代码(虽说这也是一个技巧),代码结合图示的学习方法是相当重要的,弄懂原理才是编写代码的基础。

  3.你可以做一些适当的摘抄,虽然有的时候笔记记一次以后不再阅读,但是在写字的时候也是一种加强记忆的过程,笔记的过程就可以加强你的理解。

  希望你不负此行。

                                           好了今天带大家刷几道牛客网上的算法题练练手。

单链表相关经典算法OJ题1:    203. 移除链表元素 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/remove-linked-list-elements/description/

这里给大家提供两个思路:

思路一:遍历原链表,遇见val就删除val节点的操作。

思路二:创建一个新链表,遍历原链表,找不为val的节点,尾插到新链表中。

由于第一个思路,改变指针指向,非常麻烦,我们选用思路二解决问题。

1.首先newnode和newtail都指向头节点

   2. 利用pcur遍历原链表,若节点的值不为val,则尾差到新链表中,newtail往后走一格,如果值为val则不进行尾插。遍历结束应为:

返回newhead即可得到新的链表。

 

  1. typedef struct ListNode ListNode;
  2. struct ListNode* removeElements(struct ListNode* head, int val) {
  3. ListNode*newhead,*newtail;
  4. newhead=newtail=NULL;
  5. ListNode*pcur=head;
  6. while(pcur)
  7. {
  8. //判断是否为val
  9. if(pcur->val!=val)
  10. {
  11. if(newhead==NULL)
  12. {
  13. newhead=newtail=pcur;
  14. }
  15. else{
  16. newtail->next=pcur;
  17. newtail=newtail->next;
  18. }
  19. }
  20. pcur=pcur->next;
  21. }
  22. if(newtail)
  23. {
  24. newtail->next=NULL;
  25. }
  26. return newhead;
  27. }

 单链表相关经典算法OJ题2:

876. 链表的中间结点 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/middle-of-the-linked-list/description/

思路一:统计链表的节点个数,通过除2得到中间节点。

思路二:快慢指针,慢指针每次走一步,快指针每次走两步,当快指针走到尾节点时,慢指针刚走到中间节点。

快慢指针是一个比较重要的算法技巧,我们应当熟悉掌握这个算法的技巧。 

 

 

 

  1. typedef struct ListNode ListNode;
  2. struct ListNode* middleNode(struct ListNode* head) {
  3. ListNode *slow,*fast;
  4. slow=fast=head;
  5. while(fast&&fast->next)
  6. {
  7. slow=slow->next;//
  8. fast=fast->next->next;//
  9. }
  10. return slow;
  11. }

 

 

这样就通过了。

单链表相关经典算法OJ题3:

206. 反转链表 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/reverse-linked-list/description/

思路一:创建新链表,遍历原链表的节点将其插入到新的链表中。

思路二:创建三个节点,分别记录前驱节点,当前节点,后继节点,改变原链表指针指向

我们这里采用思路二解题:

 

  1. typedef struct ListNode ListNode;
  2. struct ListNode* reverseList(struct ListNode* head) {
  3. if(head==NULL)
  4. {
  5. return head;
  6. }
  7. //创建三个节点
  8. ListNode* n1,*n2,*n3;
  9. n1=NULL,n2=head,n3=head->next;
  10. //遍历原链表,修改指针的指向
  11. ListNode*pcur=head;
  12. while(n2)
  13. {
  14. //修改n2的指向
  15. n2->next=n1;
  16. //修改三个指针的位置
  17. n1=n2;
  18. n2=n3;
  19. if(n3)
  20. {
  21. n3=n3->next;
  22. }
  23. }
  24. return n1;
  25. }

 

好了,今天就分享这些了,感谢大家观看,有问题,随时评论区提问哦。

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/87239
推荐阅读
相关标签
  

闽ICP备14008679号