leetcode刷题---链表

目录

  • 1.删除链表的倒数第N个节点
  • 两两交换链表中的节点
  • 反转链表2

1.删除链表的倒数第N个节点

在这里插入图片描述

根据题目描述,第一个思路是存到数组中对数组进行操作,想到数组我们就可以想到下标和倒数第N个的关系,所以我们可以不额外开空间,可以直接遍历数组求出倒数第N个和链表size之间的关系,然后遍历数组,找到倒数第N个是正数第多少个就可以直接删除那个位置的节点,注意,我们还需要用一个结构体指针变量记录前一个位置。

代码展示:

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    int size=0;//链表大小
    struct ListNode*cur=head;//遍历链表需要的指针
    //求出链表大小
    while(cur)
    {
        cur=cur->next;
        size++;
    }
    //特殊处理:当删除的是最后一个节点的时候,直接删除最后一个位置的节点
    if(n==size)
    {
        struct ListNode*newhead=head->next;
        free(head);
        return newhead;
    }
    int i=size-(n-1);//找出i和size的关系
    struct ListNode*prev=NULL;
    cur=head;
    //遍历数组
    while(i!=1)
    {
        prev=cur;//记录前一个位置
        cur=cur->next;
        i--;
    }
    struct ListNode*next=cur->next;
    free(cur);
    prev->next=next;
    return head;
}

两两交换链表中的节点

在这里插入图片描述

分析题目:题目的要求是让我们交换节点,注意:不是交换节点的值,而是节点之间的交换,首先我们先讨论特殊情况,如果链表为空或者链表只有一个节点则不用交换直接返回头节点,一般情况:我们可以定义一个fast(快指针),然后前后交换了之后,fast走两步,直接就来到了下一个交换的位置,用tmp记录下下个节点的值,这样才能将链表前面的值串起来,==注意:有一种特殊情况,当链表的节点是奇数个的时候最后一个节点不需要交换,所以循环中的终止条件有两个一个是:fast!=NULL还有一个是fast->next,接下来完善代码即可。

代码展示

struct ListNode* swapPairs(struct ListNode* head) {
	//特殊情况处理
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    //定义fast指针
    struct ListNode*fast=head;
    while(fast!=NULL)
    {
        if(fast->next==NULL)//奇数情况讨论
        {
            break;
        }
        //交换前后节点
        int tmp=fast->val;
        fast->val=fast->next->val;
        fast->next->val=tmp;
        fast=fast->next->next;
    } 
    return head;
}

在这里插入图片描述

题目分析:将小于k的值放在链表左边,将大于或者等于k的值放在链表右边

思路:这里我们需要的6个变量,一个是小于k的链表的头EH,还有尾ET,一个是大于或等于k的头MH和尾MT,还有一个用于遍历链表的变量cur,还有一个变量就是记录cur的下一个位置的变量next,将除了cur以外的变量置为空,然后当遍历数组的时候访问每个节点的val,如果值小于k则用EH和ET连接,如果大于或者等于k的链表,则用MH和MT连接起来,最后将两个链表重新连接起来,最后返回头节点EH。
下图展示思路过程:在这里插入图片描述
代码展示

struct ListNode* partition(struct ListNode* head, int x) {
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    //小于K的头和尾
    struct ListNode*EH=NULL;
    struct ListNode*ET=NULL;
    //大于或等于K的头和尾
    struct ListNode*MH=NULL;
    struct ListNode*MT=NULL;
    //遍历链表的变量和记录下一个节点的变量
    struct ListNode*cur=head;
    struct ListNode*next=NULL;
    while(cur)
    {
        next=cur->next;
        //判断之后连接
        if(cur->val<x)
        {
            if(EH==NULL&&ET==NULL)
            {
                EH=ET=cur;
                ET->next=NULL;
            }
            else
            {
                ET->next=cur;
                ET=cur;
                ET->next=NULL;
            }
        }
        else{
            if(MH==NULL&&MT==NULL)
            {
                MH=MT=cur;
                MT->next=NULL;
            }
            else{
                MT->next=cur;
                MT=cur;
                MT->next=NULL;
            }
        }
        cur=next;
    }
    //讨论当没有小于K的值的节点时返回大于或者等于K的链表的头
    if(EH==NULL)
    {
        return MH;
    }
    //返回链表头节点
    ET->next=MH;
    return EH;
}

反转链表2

在这里插入图片描述

思路:将链表left前面的节点封装成一个链表,将left和right中间的链表进行翻转,也就是头插,将right后面的节点封装成一个链表,然后将三个链表连接起来返回头结点,方法和上面的隔离链表类似

代码展示

struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    if(head->next==NULL||head==NULL)
    {
        return head;
    }
    struct ListNode*midH=NULL;
    struct ListNode*midT=NULL;
    struct ListNode*leftH=NULL;
    struct ListNode*leftT=NULL;
    struct ListNode*rightH=NULL;
    struct ListNode*rightT=NULL;
    struct ListNode*cur=head;
    struct ListNode*next=NULL;
    int n=1;
    while(cur)
    {
        next=cur->next;
        if(n<left)
        {
            if(leftH==NULL&&leftT==NULL)
            {
                leftH=leftT=cur;
                leftT->next=NULL;
            }
            else
            {
                leftT->next=cur;
                leftT=cur;
                leftT->next=NULL;
            }
        }
        else if(n>=left&&n<=right)
        {
            if(midT==NULL&&midH==NULL)
            {
                midH=midT=cur;
                midT->next=NULL;
            }
            else
            {
                cur->next=midH;
                midH=cur;
            }
        }
        else{
            if(rightH==NULL&&rightT==NULL)
            {
                rightH=rightT=cur;
                rightT->next=NULL;
            }
            else{
                rightT->next=cur;
                rightT=cur;
                rightT->next=NULL;
            }
        }
        n++;
        cur=next;
    }
    if(leftH==NULL)
    {
        midT->next=rightH;
        return midH;
    }
    leftT->next=midH;
    midT->next=rightH;
    return leftH;
}

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

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

相关文章

vuex插件实现数据共享

vuex插件 vuex是管理多个vue通用的数据的插件.(状态管理工具,状态是数据) 我们对于多个vue文件之间的共同数据,是用props传递,或者对于一个vue实例对象,进行绑定,传参,也是多次传参,多个文件之间,比较麻烦. 但是我们vuex会创建一个公共对象,从这个公共对象上赋值,比较简单易…

appium辅助自动化工具-- Appium studio

这里我要给大家介绍一款appium辅助自动化测试工具appium studio&#xff0c;你没看错&#xff0c;不是android studio&#xff0c;也不是appium android studio&#xff0c;就是appium studio&#xff01; 下载地址&#xff1a; Appium Studio | Digital.ai Continuous Test…

【应用笔记】LAT1413+快速开关蓝牙导致设备无广播

1. 问题背景 客户使用 BlueNRG-345MC 开发了一个 BLE 外设&#xff0c;和手机连接。在测试中发现&#xff0c;手机连接上外设之后&#xff0c;不断地在手机上点击蓝牙的开关按钮&#xff0c;造成设备不断地断开、重连&#xff1b;少则几次&#xff0c;多则几十次。点击之后&am…

【小贪】万字长文介绍因果推断和增益模型

文章目录 因果推断和增益模型1. 绪论2. 因果推断基础3. 主要增益模型3.1 Meta Learning3.1.1 S-Learner&#xff08;One Model&#xff09;3.1.2 T-Learner&#xff08;Two Model&#xff09;3.1.3 R-Learner3.1.4 X-Learner3.1.5 类别转换法&#xff08;Class Transformation …

2024年noc指导教师认证测评参考试题题目5-6合集

[noc指导教师认证] 测评参考试题 说明:NOC教师指导认证考试题目是从题库里抽题,因此每位老师每次考试题目都不一样以下题目为测试考试时收集到的一些题目,作为辅助提供给各位老师,老师们可以记住题目及答案的具体内容 (选项顺序会变),以免考试时遇到。2024年的做的题目有的…

.Websalm勒索病毒数据恢复|金蝶、用友、管家婆、OA、速达、ERP等软件数据库恢复

导言&#xff1a; 在数字化时代&#xff0c;网络安全问题日益凸显&#xff0c;其中勒索病毒作为一种新型的电脑病毒&#xff0c;以其独特的传播方式和恶劣的性质&#xff0c;给广大用户带来了巨大的困扰。近期&#xff0c;Websalm勒索病毒成为了公众关注的焦点&#xff0c;其强…

【图轮】【 最小生成树】【 并集查找】1489. 找到最小生成树里的关键边和伪关键边

本文涉及知识点 图轮 最小生成树 并集查找 关键边 1489. 找到最小生成树里的关键边和伪关键边 给你一个 n 个点的带权无向连通图&#xff0c;节点编号为 0 到 n-1 &#xff0c;同时还有一个数组 edges &#xff0c;其中 edges[i] [fromi, toi, weighti] 表示在 fromi 和 to…

【C++庖丁解牛】自平衡二叉搜索树--AVL树

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 前言1 AVL树的概念2. AVL…

【A-006】基于SSH的新闻发布系统(含论文)

【A-006】基于SSH的新闻发布系统&#xff08;含论文&#xff09; 开发环境&#xff1a; Jdk7(8)Tomcat7(8)MySQLIntelliJ IDEA(Eclipse) 数据库&#xff1a; MySQL 技术&#xff1a; SpringStruts2HiberanteJSPJquery 适用于&#xff1a; 课程设计&#xff0c;毕业设计&…

玩转Django分页器

一、Pagination 分页器编程步骤 View, 导入django.core.paginator.Paginator类&#xff0c;创建Paginator 对象时&#xff0c;输入qs对象&#xff0c;以及每页显示条数。 接收 URL, 从请求参数中读取page数值 &#xff0c;通过 paginator.page(page_num) 返回请求页的page_obj…

ObjectiveC-05-复杂和特殊数据类型

这一节中会详细介绍下ObjectiveC中的复杂数据类型&#xff0c;这些类型不太是太归类。但非常有用&#xff0c;有的用于定义变量、有的则是专门用于方法的返回值。 常用的大概有如下这些&#xff1a; 以上这些特殊的数据类型都可用于变量、方法返回值、方法参数使用&#xff0c…

目标伪类选择器

E:target选择匹配E的所哟元素&#xff0c;且匹配元素被相关url指向 鼠标点击右边京东秒杀跳转到京东秒杀div&#xff0c;并变成黄色 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport&…

HTML块级元素和内联元素(头部和布局)

目录 1.HTML块级和内联标签&#xff1a; 1.块级元素&#xff1a; 2.内联元素: 3.元素嵌套&#xff1a; 4.元素转换&#xff1a; 示例如下: 2.内联框架&#xff1a; 前言&#xff1a; 示例如下: 3.布局&#xff1a; 4.头部标签&#xff1a; 前言&#xff1a; 说明&…

Java获取当前时间

获取当前的时间 在Java中获取时间和日期使用Date类中的 toString方法 import java.util.Date;public class DateDemo {public static void main(String[] args) {Date date1new Date();System.out.println(date1.toString());} } 进一步格式化时间 SimpleDateFormat 是格式化…

Netty组件优化之FastThreadLocal

ThreadLocal:CSDNhttps://mp.csdn.net/mp_blog/creation/editor/132995427 Netty中的FastThreadLocal是对Java中的FastThreadLocal的优化主要是为了解决ThreadLocal中线性查找 带来的性能下降同时实现快速查找和赋值 FastThreadLocal构建这里的index代表一个编号&#xff0c;从…

ROS机器人入门第五课:话题通信自定义msg

文章目录 ROS机器人入门第五课&#xff1a;话题通信自定义msg一、介绍二、流程&#xff08;一&#xff09;定义msg文件&#xff08;二&#xff09;编辑配置文件&#xff08;三&#xff09;编译 三、话题通信自定义msg调用&#xff08;一&#xff09;调用流程0.vscode配置1.发布…

论文笔记 - :MonoLSS: Learnable Sample Selection For Monocular 3D Detection

论文笔记✍MonoLSS: Learnable Sample Selection For Monocular 3D Detection &#x1f4dc; Abstract &#x1f528; 主流做法限制 &#xff1a; 以前的工作以启发式的方式使用特征来学习 3D 属性&#xff0c;没有考虑到不适当的特征可能会产生不利影响。 &#x1f528; 本…

基于java+SpringBoot+Vue的网上书城管理系统设计与实现

基于javaSpringBootVue的网上书城管理系统设计与实现 开发语言: Java 数据库: MySQL技术: SpringBoot MyBatis工具: IDEA/Eclipse、Navicat、Maven 系统展示 前台展示 后台展示 系统简介 整体功能包含&#xff1a; 网上书城管理系统是一个基于互联网的在线购书平台&#…

基于springboot实现旅游网站系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现旅游网站系统演示 摘要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff0c;旅游网站当然也不能排除在外&#xff0c;随着旅游网站的不断成熟&#xff0c;它彻底改变了过去传统的旅游…

CI/CD实战-jenkins结合ansible 7

配置主机环境 在jenkins上断开并删除docker1节点 重新给master添加构建任务 将server3&#xff0c;server4作为测试主机&#xff0c;停掉其上后面的docker 在server2&#xff08;jenkins&#xff09;主机上安装ansible 设置jenkins用户到目标主机的免密 给测试主机创建用户并…