力扣刷题---初始链表1

在这里插入图片描述

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏: 🍔🍟🌯 c语言初阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:讲解初始数据结构链表的三个力扣题
1.移除链表元素.
2.反转链白哦.
3.链表的中间结点.
金句分享:
✨追光的人,终会光芒万丈!✨

目录

  • 一、移除链表元素
    • 题目描述
    • 示例
    • 图解:
    • 代码:
  • 二、反转链表
    • 题目描述:
    • 示例
    • 图解:
    • 代码:
  • 三、链表的中间结点
    • 题目描述:
    • 示例:
    • 代码1:
    • 代码2:

一、移除链表元素

题目:传送门

题目描述

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

示例

示例 1:
在这里插入图片描述

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

示例2:

输入:head = [7,7,7,7], val = 7
输出:[]

思路:

1.创建一个cur指针=head,用于代替head往后遍历寻找结点的val值为val的目标结点.
2.创建一个prev指针,初始化为NULL,用于跟在cur后面,负责改变要删除的目标结点的前驱的next.
3.当cur为目标结点时,使目标结点的前驱(prev)的next跳过目标结点(cur),指向目标结点的下一个节点(cur->next).
4.释放掉cur所指向的目标结点(此时prev->next为cur的下一个结点),由于cur被释放掉了,cur要继续往后走的时候,需要借助prev即(cur=prev->next)
5.直到cur=NULL结束循环.

图解:

在这里插入图片描述

代码:

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*cur=head;//代替head遍历链表
    struct ListNode*prev=NULL;//记录目标结点的前驱,并使其的next跳过目标结点
    while(cur)//循环条件是cur不指向空
    {
        if(cur->val!=val)//如果不是目标结点
        {
            prev=cur;//cur往后走之前记录位置
            cur=cur->next;//cur往后走
        }
        else
        {
            if(prev==NULL)//如果第一个节点就等于val,这时的prev为NULL
            {
            	//用于头删
                head=cur->next;//记录头结点的后继
                free(cur);//释放头结点
                cur=head;//使头指针指向第二个结点
            }
            else 
            {
            //此时cur为要删除的目标结点
             	prev->next=cur->next;//使得目标结点的前驱的next指向目标结点的下一个结点
            	free(cur);//释放掉要删除的结点
            	cur=prev->next;//接触prev使cur往后走.
            }
        }
    }
    return head;//最后返回头结点
}

二、反转链表

题目:传送门

题目描述:

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例

在这里插入图片描述

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

输入:head = [1,2]
输出:[2,1]

思路:

1.创建一个记录前驱的指针prev,初始值应为NULL,即第一个结点改变后指向的前驱
2.创建一个遍历链表的指针cur,作用是改变其指向的结点的next,初始值应该为head即第一个要改变的结点.
3.创建一个记录后继的指针tail,初始值为,head->next,用于记录后继,否则cur不知道后面的路在哪里了.

指针创建好后,使用cur->next = prev,改变cur结点的next指向.
更新前驱:prev = cur
cur继续往后走:cur = tail
更新后继:tail = tail->next

注意,循环体设计的条件是,cur指向NULL停止,这是,tail已经为空,所以要限制一下条件.只有当还有后继即tail不为空时,才保留后继.

图解:

在这里插入图片描述

代码:

struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)//防止传入空链表
    {
        return NULL;
    }
    struct ListNode* prev = NULL;//记录前驱结点
    struct ListNode* cur = head;//遍历链表
    struct ListNode* tail = head->next;//记录后继结点
    while (cur)
    {
        cur->next = prev;//使得结点的next指向它的前驱
        prev = cur;//更新前驱
        cur = tail;//cur往后走
        if(tail)tail = tail->next;//更新后继
    }
    return prev;
}

三、链表的中间结点

题目描述:

给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。

示例:

在这里插入图片描述

输入:head = [1,2,3,4,5]
输出:[3,4,5]
解释:链表只有一个中间结点,值为 3 。

在这里插入图片描述

输入:head = [1,2,3,4,5,6]
输出:[4,5,6]
解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。

常规思路:

创建指针cur代替head遍历链表
先遍历一遍链表,计算链表的长度,得到length.
使cur重新赋值为head
使cur往后走length/2步便可以得到中间结点.
最后返回cur

代码1:

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*cur=head;
    int length=0;
    while(cur!=NULL)//计算链表的长度
    {
        cur=cur->next;
        length++;
    }
    length=length/2;
    cur=head;//重新赋值
    while(length--)//往后走length/2步
    {
        cur=cur->next;
    }
    return cur;//返回中间结点
}

思路2:快慢指针

定义一个slow(慢指针)指针
定义一个fast(快指针)指针
两个指针都是从head指向的结点出发,fast一次走两步,slow一次走一步,当fast走向NULL的时候,slow刚好走到中间结点处.

建议画图分析链表的长度为奇数和偶数情况.

代码2:

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

结语:
对于数据结构初学者,链表的oj题对于帮助掌握链表还是很有好处的.可以帮助自己更好的理解和掌握链表.
还有,快慢指针的使用是一个很好的思想,在很多情况下时可以给我们带来便利,不要仅限于快指针永远都只会走两步的固定思想哦!
886
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/945.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Visual Studio Code 1.76 发布

欢迎使用 Visual Studio Code 2023 年 2 月版,其中一些亮点包括: 配置文件 - 活动配置文件徽章,通过命令面板快速切换配置文件。辅助功能改进 - 新的音频提示,改进的终端屏幕阅读器模式。可移动的 Explorer 视图- 将资源管理器放…

JavaWeb——Request(请求)和Response(响应)介绍

在写servlet时需要实现5个方法,在一个service方法里面有两个参数request和response。 浏览器向服务器发送请求会发送HTTP的请求数据——字符串,这些字符串会被Tomcat所解析,然后这些请求数据会被放到一个对象(request)里面保存。 相应的Tom…

有图解有案例,我终于把 Condition 的原理讲透彻了

哈喽大家好,我是阿Q! 20张图图解ReentrantLock加锁解锁原理文章一发,便引发了大家激烈的讨论,更有小伙伴前来弹窗:平时加解锁都是直接使用Synchronized关键字来实现的,简单好用,为啥还要引用Re…

React面向组件编程(理解与使用+state+props+refs与事件处理)

1 基本理解与使用 函数式组件 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"…

开发板与ubantu文件传送

接下来的所以实验都通过下面这种方式发送APP文件到开发板运行 目录 1、在ubantu配置 ①在虚拟机上添加一个桥接模式的虚拟网卡 ②设定网卡 ③在网卡上配置静态地址 2、开发板设置 ①查看网卡 ②配置网卡静态ip 3、 测试 ①ping ②文件传送 传送报错情况 配置环境&#…

Java Web 实战 14 - 计算机网络之初识计算机网络

初识计算机网络一 . 网络发展史二 . 局域网 VS 广域网2.1 交换机与路由器2.2 集线器三 . 网络通信基础3.1 协议3.1.1 OSI 七层模型3.1.2 TCP / IP 五层模型3.2 交换机和路由器的区别3.3 封装和分用大家好 , 这篇文章给大家分享的是计算机网络的一些基础知识 , 我们会给大家分享…

钉钉,下沉进农田

在这个古老的产业里&#xff0c;数字化没有被放到更高的位置&#xff0c;但难点依旧存在。钉钉恰是基于它足够柔性的产品特性和普惠的服务模式&#xff0c;真正帮助农食产业中的人和企业解决着过去一直没有解决的问题&#xff0c;让这个产业中的人和环节都向数字化潮水迈进了一…

linux目录——文件管理

个人简介&#xff1a;云计算网络运维专业人员&#xff0c;了解运维知识&#xff0c;掌握TCP/IP协议&#xff0c;每天分享网络运维知识与技能。座右铭&#xff1a;海不辞水&#xff0c;故能成其大&#xff1b;山不辞石&#xff0c;故能成其高。个人主页&#xff1a;小李会科技的…

CGAL 点云上采样

目录一、算法原理1、主要函数2、参数解析二、代码实现三、结果展示一、算法原理 该方法对点集进行逐步上采样&#xff0c;同时根据法向量信息来检测边缘点&#xff0c;需要输入点云具有法线信息。在点云空洞填充和稀疏表面重建中具有较好的应用。 1、主要函数 头文件 #inclu…

最强分布式锁工具:Redisson

1 Redisson概述1.1 什么是Redisson&#xff1f;Redisson是一个在Redis的基础上实现的Java驻内存数据网格&#xff08;In-Memory Data Grid&#xff09;。它不仅提供了一系列的分布式的Java常用对象&#xff0c;还提供了许多分布式服务。其中包括(BitSet, Set, Multimap, Sorted…

GPT-4测评,大家先别急,图片输入还没来

昨天GPT-4朋友圈刷屏&#xff0c;我更新了一篇小文章&#xff0c;极简罗列GPT-4的一些情报&#xff1a; 1 ChatGPT Plus用户才可试用GPT-4 2 试用阶段每四小时最多100条信息 3 知识库还是2021年 4 上下文长度为8192个token 5 是多模态&#xff0c;但是图片输入仍处于研究预…

排序算法之插入排序

要考数据结构了&#xff0c;赶紧来复习一波排序算法 文章目录一、直接插入排序二、希尔排序一、直接插入排序 直接上主题 插排&#xff0c;揪出一个数&#xff0c;插入到原本已经有序的数组里面&#xff0c;如数组有n个数据&#xff0c;从0~n下标依次排列&#xff0c;先从左往…

iOS中SDK开发 -- cocoapods库创建

在iOS项目中&#xff0c;经常使用cocoadpods来进行依赖管理以及三方库引入等。引入的三方库一般会有几种形式&#xff1a;一、在Pods目录下可以直接看到源代码的开源库&#xff0c;如AFNetworking&#xff0c;Masonry等常见开源库。二、在Pods目录下拉取的项目文件只能看到对应…

讲解Linux中samba理论讲解及Linux共享访问

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的绽放&#xff0…

监管数据治理治什么?1104、EAST、客户风险系统数据简介

近年来&#xff0c;随着经济社会数字化发展&#xff0c;商业银行逐步向数字化、智能化转型&#xff0c;监管部门对商业银行数据报送质量也越来越重视。自2020年5月9日工行、农行、中行、建行、交行、邮储、中信、光大8家商业银行因监管标准化数据&#xff08;EAST&#xff09;系…

漫画:什么是归并排序算法?

归并排序是建立在归并操作的一种高效的排序方法&#xff0c;该方法采用了分治的思想&#xff0c;比较适用于处理较大规模的数据&#xff0c;但比较耗内存&#xff0c;今天我们聊聊归并排序 一、排序思想 一天&#xff0c;小一尘和慧能坐在石头上&#xff0c;眺望着远方 分而治…

Qt5.12实战之QByteArray与字符指针及字符串转换

示例源码:#include <QCoreApplication> #include <QDebug> #include <QTextStream> static QTextStream cout (stdout,QIODevice::WriteOnly); #include <iostream> #include <QtGlobal> #include <QByteArray>void test() {qDebug() <…

进程调度的基本过程

这里写目录标题什么是进程进程管理结构体或类的主要属性pid内存指针文件描述符表辅助进程调度的属性并发并行并发什么是进程 进程是操作系统对一个正在运行的程序的一种抽象&#xff0c;也就是说&#xff0c;一个运行起来的程序就是一个进程。 进程又是操作系统进行资源分配的…

百度终于要出手了?文心一言

文心一言 百度全新一代知识增强大语言模型&#xff0c;文心大模型家族的新成员&#xff0c;能够与人对话互动&#xff0c;回答问题&#xff0c;协助创作&#xff0c;高效便捷地帮助人们获取信息、知识和灵感。 前几天炒的风风火火的ChatGPT&#xff0c;虽然 ChatGPT 很强大&a…

【Error: ImagePullBackOff】Kubernetes中Nginx服务启动失败排查流程

❌pod节点启动失败&#xff0c;nginx服务无法正常访问&#xff0c;服务状态显示为ImagePullBackOff。 [rootm1 ~]# kubectl get pods NAME READY STATUS RESTARTS AGE nginx-f89759699-cgjgp 0/1 ImagePullBackOff 0 103…
最新文章