【每日易题】数据结构链表篇——单链表oj题（1），几道典型例题带你快速掌握单链表

在这里插入图片描述

君兮_的个人主页

勤时当勉励岁月不待人

C/C++ 游戏开发

Hello,米娜桑们，这里是君兮_，今天来填一个埋了好久的坑，在暑假之前就预告过这个系列，但由于各种原因（主要是有点懒）今天才开坑。我们这个系列主要是根据博主自身的编程学习的经历来带大家分模块来刷一些经典的题型，通过做题来加深大家对该部分内容的掌握。
好了，废话不多说，开始今天的学习吧！—

我们的刷题顺序是从入门到入土，其中前面入门的内容与后面入土的内容有些还有一定的联系，能直接帮助你入土哦！！！(好了，不开玩笑，只要你好好琢磨琢磨这些题你都能独立完成的)

一.移除链表元素

本题oj链接如下：移除链表元素
其中关于题目的文字描述并不难理解，通过结合给的示例我们知道本题想要删除链表中所有等于val的值，返回把剩下节点连在一起的头节点。
下面提供改题目的解答思路以及代码实现
1.该题其实与我们之前讲的单链表的中间删除非常相似，只不过我们的中间删除是通过地址来找到需要删除的位置，而本题需要的找到节点中等于val的值删除，我们只需要让等于val的节点的前一个节点跳过值等于val的节点指向val下一个节点，最后再把等于val的节点free释放掉即可

struct ListNode* removeElements(struct ListNode* head, int val) {
    if(head == NULL)//链表中什么都没有
        return NULL;
    
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    
    while(cur)
    {
        //如果当前节点是需要删除的节点
        if(cur->val == val)
        {
            //首先保存下一个节点
            struct ListNode* next = cur->next;
            //如果删除的为头节点，更新头节点
            //否则让当前节点的前趋节点链接next节点
            if(prev == NULL)
            {
                head = cur->next;
            }
            else
            {
                prev->next = cur->next;  
            }
            //释放当前节点，让cur指向next
            free(cur);
            cur = next;
        }
        else
        {
            //如果cur不是需要删除的节点，则更新prev,cur
            prev = cur;
            cur = cur->next;
        }
    }
    
    return head;//返回新头
}

在这里插入图片描述

二.反转链表

本题oj链接如下：反转链表
该题有两种思路，我们分别来介绍一下，并代码实现
1.链表中有一种插入方式叫头插，顾名思义就是在头部进行节点的插入，比如你在链表中依次头插 1 2 3 4 5，那么其实在链表中其实是反过来依次从头插的，也就是 5 4 3 2 1.这与我们这题想要我们实现的反转链表不就对上了吗？

struct ListNode* reverseList(struct ListNode* head){
    //把原链表中的节点依次头插入新链表中
    struct ListNode*newnode=NULL;
    struct ListNode*cur1=head;
    while(cur1)
    {
        //头插 
      struct ListNode*next=cur1->next;
           
            cur1->next=newnode;
            newnode=cur1;
            cur1=next;
        
    }
    return newnode;
   
}

在这里插入图片描述

2.通过三个指针倒转该链表，我们假设此时有三个指针，其中n1指向head，n2指向n1的next，n3指向n2的next，此时逻辑图如图所示。
我们想要该链表反转，我们可以让链接两个节点的箭头转向，用c语言的话来说，就是让该节点的指针从指向下一个节点变为指向上一个节点，由于此时的1变为了新的尾，我们把1的next置空，如图`
当我们完成这一步后，下面我们需要把三个指针都往前走一步，让链表中未反转的节点也反转一下

在这里插入图片描述

我们的结束条件是什么呢？当我们的n1是最后一个节点时，说明我们链表中所有的节点都已经反转完成，此时是不是就可以停了？此时由于n2为的前一位，也就是n2为空时，n1就来到了我们的最后一位，因此我们可以把n2为空作为循环停止的条件

在这里插入图片描述

struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL || head->next == NULL)//说明此时只有一个节点或者没有节点，直接返回head即可
        return head;
    
    struct ListNode* n1, *n2, *n3;
    n1 = head;
    n2 = n1->next;
    n3 = n2->next;
    n1->next = NULL;
    //中间节点不为空，继续修改指向
    while(n2)
    {
        //中间节点指向反转
        n2->next = n1;
        //更新三个连续的节点
        n1 = n2;
        n2 = n3;
        if(n3)//防止n3越界，判断一下n3是否为空
            n3 = n3->next;
    }
    //返回新的头
    return n1;
}

在这里插入图片描述

3.链表的中间结点

oj链接如下：链表的中间结点
这个oj题同样有两种解法，我们还是来一种一种的分析
1.暴力求解法
题目要求的是找到链表的中间结点，那么我们首先可以先遍历一遍链表同时计数，以此达到记录链表中有多少结点的目标，之后我们在取计数的一半，让链表遍历一半，此时的结点就是我们的中间结点啦!

struct ListNode* middleNode(struct ListNode* head){
     
        struct ListNode*cur=head;
        struct ListNode*midcur=head;
        int size=0;//标记计数
        while(cur)
        {
            size++;
            cur=cur->next;
        }
        int len=size/2;//取链表节点数的一半找到中间结点
        while(len)
        {
            midcur=midcur->next;
            len--;
        }
        return midcur;
}

在这里插入图片描述

第二种方法就比较巧妙了，我们现在来通过一个实际的例子来帮助大家理解。
某天，一个老和尚测试一个小和尚几个问题，并要求他在半炷香内回答出来，此时老和尚委托你来负责计时，但是由于寺庙里香不够了，只有一炷香供你计时，那么此时你应该怎么做呢？
答案是：从两头同时开始烧
这个实际的例子有没有带给你什么启发呢？我们同样是需要求链表的中间结点，也就是一半。
揭晓答案：使用快慢指针，快的一次走两步，慢的一次走一步，当快的走到尾时，慢的指针此时就在中间结点。
类比一下，此时快指针就是从两头烧，慢指针是从一头烧，当两头烧完时，就相当于一头烧烧完了半炷香！！

struct ListNode* middleNode(struct ListNode* head){
     
       struct ListNode*fast,*slow;
        fast=slow=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
}