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

简介: 【每日易题】数据结构链表篇——单链表oj题(1),几道典型例题带你快速掌握单链表

一.移除链表元素

其中关于题目的文字描述并不难理解,通过结合给的示例我们知道本题想要删除链表中所有等于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;
}


总结

  • 今天的内容到这里就结束了,一次讲多了大家可能会贪多嚼不烂,所以暂时先介绍这三个典型的题,之后也会继续更新有关的其他题目。
  • 切记如果你想要真正学好的话一定要自己动手试试哦,光看不自己写是永远学不会的!!
  • 好了,如果你有任何疑问欢迎在评论区或者私信我提出,大家下次再见啦!


目录
相关文章
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
57 4
|
1天前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
27天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
53 5
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
95 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
49 0
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
68 0
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
27 0
|
2月前
|
存储
数据结构(单链表)
数据结构(单链表)
23 0

热门文章

最新文章