[LeetCode]-链表中倒数第k个结点-CM11 链表分割-LCR 027. 回文链表

目录

链表中倒数第k个结点

题目

思路

代码

CM11 链表分割

题目

思路

代码 

LCR 027.回文链表

 题目

思路

代码


链表中倒数第k个结点


链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)icon-default.png?t=N7T8https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

题目

输入一个链表,输出该链表中倒数第k个结点。

示例:

输入:1,{1,2,3,4,5}

返回值:{5}

思路

创建两个结构体指针fast和slow指向头节点,先让fast往后遍历,fast通过while循环先走k步后停止,fast和slow同时走,当fast为NULL时,slow所在位置就是倒数第k个。

图示如下👇

代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast=pListHead,* slow=pListHead;
    while(fast)
    {         
        fast=fast->next;
        k--;
        if(k<0)
        slow=slow->next;
    }
    if(k>0)
    { 
     return NULL;
    }
    return slow;  
}

CM11 链表分割

链表分割_牛客题霸_牛客网 (nowcoder.com)icon-default.png?t=N7T8https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

题目

现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

示例:

输入:{1,2,3,5,1}

返回值:{1,2,1,3,5}

思路

定义两个哨兵节点,将原链表中节点值大于x和小于x的分别接入两个哨兵节点后,再将大于x的链表去掉哨兵节点后接到小于x的链表后面,要注意的是,记得将新链表最后一个节点置空,不然容易成环。

图示如下👇

代码 

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* ghead,*gtail,*lhead,*ltail;
        ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));
        lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                gtail->next=cur;
                gtail=gtail->next;
            }
            else
            {
                ltail->next=cur;
                ltail=ltail->next;
            }
            cur=cur->next;
        }
        gtail->next=lhead->next;

        ltail->next=NULL;
        struct ListNode* head=ghead->next;
        free(lhead);
        free(ghead);

        return head;
    }
};

LCR 027.回文链表

 LCR 027. 回文链表icon-default.png?t=N7T8https://leetcode.cn/problems/aMhZSa/

 题目

给定一个链表的 头节点 head ,请判断其是否为回文链表。

如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。

示例:

思路

判断链表是否是回文结构,我们可以先找出中间节点mid,从中间节点开始后半段逆置处理,得到新的中间节点rmid,我们可以从整个链表头节点head和rmid开始遍历比较head->val和rmid->val是否相等,若直到rmid->next==NULL时均相等,则为回文结构返回true,反之则直接跳出遍历循环,返回false。

由于代码过长,为了代码更加条理和简洁,找出中间节点和逆置的步骤,我们可以用包装函数的方法实现。

代码

//找中间节点
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

//逆置
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while (cur) {
        //保存下一节点
        struct ListNode* next = cur->next;

        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

bool isPalindrome(struct ListNode* head){
    struct ListNode* mid=middleNode(head);
    struct ListNode* rmid=reverseList(mid);
    while(head&&rmid)
    {
        if(head->val!=rmid->val)
        {
            return false;
        }
        head=head->next;
        rmid=rmid->next;
    }
    return true;
}

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

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

相关文章

YOLO目标检测数据集大全【含voc(xml)、coco(json)和yolo(txt)三种格式标签+划分脚本+训练教程】(持续更新建议收藏)

一、作者介绍&#xff1a;资深图像算法工程师&#xff0c;YOLO算法专业玩家&#xff1b;擅长目标检测、语义分割、OCR等。 二、数据集介绍&#xff1a; 真实场景的高质量图片数据&#xff0c;数据场景丰富&#xff0c;分享的绝大部分数据集已应用于各种实际落地项目。所有数据…

Technology strategy Pattern 学习笔记4 - Creating the Strategy-Corporate Context

Creating the Strategy-Corporate Context 1 •. Stakeholder Alignment 1.1 要成功&#xff0c;要尽可能获得powerful leader的支持 1.2 也需要获得最高执行层的支持 1.3 Determining&#xff08;确定&#xff09; Stakeholders 需要建立360度组织图&#xff0c;确认三类人…

GEE数据集——原住民土地(原住民土地地图)数据集

原住民土地&#xff08;原住民土地地图&#xff09; 土地承认是人们在日常生活中融入原住民存在和土地权利意识的一种方式。这通常在仪式、讲座或教育指南开始时进行。它可以是一种明确但有限的方式来认识殖民主义和第一民族的历史以及定居者殖民社会变革的需要。在这种情况下…

美团面试:Redis 除了缓存还能做什么?可以做消息队列吗?

这是一道面试中常见的 Redis 基础面试题,主要考察求职者对于 Redis 应用场景的了解。 即使不准备面试也建议看看,实际开发中也能够用到。 内容概览: Redis 除了做缓存,还能做什么? 分布式锁:通过 Redis 来做分布式锁是一种比较常见的方式。通常情况下,我们都是基于 Re…

【Mybatis小白从0到90%精讲】03:编写Mapper,第一个入门程序

文章目录 前言一、创建mysql user表二、注解方式三、XML方式四、编写main方法调用前言 映射器Mapper是 MyBatis 中最重要的文件,简单的讲主要用来映射SQL语句。 映射器有两种实现方式:注解方式、XML文件方式(推荐)。 接下来演示通过两种方式,开发Mybatis第一个入门程序,…

Python基础入门例程49-NP49 字符列表的长度

最近的博文&#xff1a; Python基础入门例程48-NP48 验证登录名与密码&#xff08;条件语句&#xff09;-CSDN博客 Python基础入门例程47-NP47 牛牛的绩点&#xff08;条件语句&#xff09;-CSDN博客 Python基础入门例程46-NP46 菜品的价格&#xff08;条件语句&#xff09;…

在Google Kubernetes集群创建分布式Jenkins(一)

因为项目需要&#xff0c;在GKE的集群上需要创建一个CICD的环境&#xff0c;记录一下安装部署一个分布式Jenkins集群的过程。 分布式Jenkins由一个主服务器和多个Agent组成&#xff0c;Agent可以执行主服务器分派的任务。如下图所示&#xff1a; 如上图&#xff0c;Jenkins Ag…

48基于matlab的经验傅里叶分解,适用于非线性及非平稳时间序列分析,将信号进行精确分解。程序已调通,可直接运行。

基于matlab的经验傅里叶分解&#xff0c;适用于非线性及非平稳时间序列分析&#xff0c;将信号进行精确分解。程序已调通&#xff0c;可直接运行。

3.26每日一题(线性非齐次的特解如何设)

1、非齐次方程有e的2x次幂&#xff1a;特解也有e的2x次幂 2、e的2x次幂前面有特殊的一元方程&#xff1a;特解要设为一般的特征方程&#xff08;axb&#xff09; 3、求线性齐次特征方程的特征根&#xff1b; 4、判断e的 rx 次幂中的 r 和特征根有没有重合的个数&#xff1a;…

私有化部署大模型:5个.Net开源项目

从零构建.Net前后端分离项目 今天一起盘点下&#xff0c;10月份推荐的5个.Net开源项目&#xff08;点击标题查看详情&#xff09;。 1、BootstrapBlazor企业级组件库&#xff1a;前端开发的革新之路 BootstrapBlazor是一个用于构建现代Web应用程序的开源框架&#xff0c;它基…

Netty第二部

一、EventLoop和EventLoopGroup 一个Channel可以近似的理解成一个Socket的包装&#xff0c;EventLoop管理这些Channel的 1、EventLoop EventLoop作为线程&#xff0c;具体Channel由EventLoop管理&#xff0c;在AbstractChannel类的register()方法可以体现 Override public …

观察者模式——解决解耦的钥匙

● 观察者模式介绍 观察者模式是一个使用频率非常高的模式&#xff0c;它最常用的地方是GUI系统、订阅——发布系统。因为这个模式的一个重要作用就是解耦&#xff0c;将被观察者和观察者解耦&#xff0c;使得它们之间依赖性更小&#xff0c;甚至做到毫无依赖。以CUI系统来说&a…

Linux安装配置awscli命令行接口工具及其从aws上传下载数据

官网技术文档有全面介绍&#xff1a;安装或更新 AWS CLI 的最新版本 - AWS Command Line Interface在系统上安装 AWS CLI。https://docs.aws.amazon.com/zh_cn/cli/latest/userguide/getting-started-install.html#getting-started-install-instructionsawscli常用命令参考&…

uni-app学习笔记

目录 一、前期准备 1、项目认识 2、pages.json基本配置 3、创建页面 二、tabBar 1、获取图标 2、代码配置 三、基础认识 1、页面生命周期 2、App.vue应用生命周期 四、基础组件 1、scroll-view可滚动视图区域 2、提示框 3、swiper滑块视图容器 4、form表单组件 一…

番外---9.0 firewall 网络

### 网络配制方式&#xff1a; 00&#xff1a;依据图形界面形式配置&#xff08;nmtui&#xff09;&#xff1b; 01&#xff1a;命令形式配置(nmcli)&#xff1b; 02&#xff1a;使用系统菜单配置&#xff1b; 00&#xff1a;依据图形界面形式配置&#xff08;nmtui&#xff0…

解决方案中word中分页符的使用

在投标方案中要善于使用“分页符”&#xff0c;尽可能少使用分节符号&#xff0c;没有分页符前&#xff0c;你每次修改你的标书或者文件&#xff0c;增加或者修改内容后。你的格式字段前后都是会发生变化&#xff0c;如何稳定的保证结构呢&#xff0c;那就是分页符的使用&#…

C语言映射表在串口数据解析中的应用

一、映射表在串口数据解析中的应用 1、数据结构 typedef struct {char CMD[CMDLen];unsigned char (*cmd_operate)(char *data); }Usart_Tab; 2、指令、函数映射表 static const Usart_Tab InstructionList[CMDMax] {{"PWON",PowOn},{"PWOFF",PowOff}…

antd的Table组件使用rowSelection属性实现多选时遇到的bug

前言 前端样式框架采用AntDesign时&#xff0c;经常会使用到Table组件&#xff0c;如果要有实现多选或选择的需求时往往就会用到rowSelection属性&#xff0c;效果如下 rowSelection属性属性值如下 问题 文档中并没有说明选择时以数据中的哪个属性为准&#xff0c;看官方案例…

docker 下安装mysql8.0

在docker中查询mysql镜像 PS C:\Users\admin> docker search mysql NAME DESCRIPTION STARS OFFICIAL AUTOMATED mysql MySQL is a widely used, open-source relation……

答题测评考试小程序的效果如何

在线答题系统是一种在线练习、考试、测评的智能答题系统&#xff0c;适用于企业培训、测评考试、知识竞赛、模拟考试等场景&#xff0c;管理员可任意组题、随机出题&#xff0c;答题者成功提交后&#xff0c;系统自动判分。 多种题目类型&#xff0c;两种答题模式 练习模式&a…