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

      之前我们对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即可得到新的链表。

 

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)icon-default.png?t=N7T8https://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;
}

 

 

这样就通过了。

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

206. 反转链表 – 力扣(LeetCode)icon-default.png?t=N7T8https://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;
}

 

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

 

版权声明:本文为博主作者:努力学编程’原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/2301_76249062/article/details/136081744

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
社会演员多的头像社会演员多普通用户
上一篇 2024年2月19日
下一篇 2024年2月19日

相关推荐

此站出售,如需请站内私信或者邮箱!