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

之前我们对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）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;
}

这样就通过了。

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

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;
}