【nowcoder】链表的回文结构

牛客题目链接 链表的回文结构
在这里插入图片描述

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstdlib>
// 建议大伙自己对照我的代码画下图,假设A链表是:1 2 3 2 1
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) { // 空间复杂度O(1)
        // 找到中间节点 (slow是3)
        ListNode* slow = A, * fast = A;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 反转后半部分 
        //(3 2 1变成1 2 3,但是A并没有变成1 2 1 2 3,A这时是1 2 3,自己画下图就知道了)
        ListNode* cur = NULL, * next = NULL;
        while (slow) {
            next = slow->next;
            slow->next = cur;
            cur = slow;
            slow = next;
        }
        // 前半部分和后半部分比较 (next = A = 1 2 3,cur = 1 2 3)
        next = A;
        while (cur) {
            if (next->val != cur->val) {
                return false;
            }
            next = next->next;
            cur = cur->next;
        }
        return true;
    }

    bool chkPalindrome_(ListNode* A) { // 空间复杂度O(n)
        // 1.创建B链表,将A链表节点依次向B链表头插
        ListNode* B = NULL;
        ListNode* curA = A;
        while (curA) {
            ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
            newNode->val = curA->val;
            newNode->next = NULL;
            if (B == NULL) {
                B = newNode;
            }
            else {
                newNode->next = B;
                B = newNode;
            }
            curA = curA->next;
        }
        // 2.比较
        curA = A;
        ListNode* curB = B;
        while (curA) {
            if (curA->val != curB->val) {
                return false;
            }
            curA = curA->next;
            ListNode* del = curB;
            curB = curB->next;
            free(del);
            del = NULL;
        }
        return true;
    }
};

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

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

相关文章

小程序系列--11.小程序自定义组件

一、组件的创建与引用 1. 创建组件 2. 引用组件 3. 局部引用组件 4. 全局引用组件 5. 全局引用 VS 局部引用 6. 组件和页面的区别 二、样式 1. 组件样式隔离 2. 组件样式隔离的注意点 3. 修改组件的样式隔离选项 4. styleIsolation 的可选值 三、数据、方法和属性 1…

初识“操作系统“(Operator System)

概念 任何计算机系统都包含一个基本的程序集合&#xff0c;称为操作系统(OS)。笼统的理解&#xff0c;操作系统包括&#xff1a; 内核&#xff08;进程管理&#xff0c;内存管理&#xff0c;文件管理&#xff0c;驱动管理&#xff09; 其他程序&#xff08;例如函数库&#xff…

【教程】如何在苹果手机上查看系统文件?

​ 目录 引言 用户登录工具和连接设备 查看设备信息&#xff0c;电池信息 查看硬盘信息 硬件信息 查看 基带信息 销售信息 电脑可对手机应用程序批量操作 运行APP和查看APP日志 IPA包安装测试 注意事项 引言 苹果手机与安卓手机不同&#xff0c;无法直接访问系统文件…

webpack常用配置

1.webpack概念 ​ 本质上&#xff0c;webpack 是一个用于现代 JavaScript 应用程序的 静态模块打包工具。当 webpack 处理应用程序时&#xff0c;它会在内部从一个或多个入口点构建一个 依赖图(dependency graph)&#xff0c;然后将你项目中所需的每一个模块组合成一个或多个 …

Kruise Rollout 全链路灰度实践

作者&#xff1a;旦酱、十眠 什么是全链路灰度&#xff1f; 在发布应用的过程中&#xff0c;我们通常希望用少量特定流量来验证新版本的发布是否正常&#xff0c;以保障整体稳定性。这个过程被称为灰度发布。关于灰度发布&#xff0c;我们通过逐步增加发布的范围&#xff0c;…

如何快速解决局域网IP冲突问题?连接IP地址冲突如何用代理IP搞定?

随着互联网的普及&#xff0c;局域网已经成为了许多家庭和企业中不可或缺的一部分。然而&#xff0c;局域网中的IP地址冲突问题却时常困扰着用户。一旦出现IP地址冲突&#xff0c;网络连接就会变得不稳定&#xff0c;甚至无法正常上网。那么&#xff0c;如何快速解决局域网IP冲…

《Linux系列》Linux虚拟机,LVM逻辑卷扩容,xfs文件系统扩容

Linux虚拟机&#xff0c;LVM逻辑卷扩容&#xff0c;xfs文件系统扩容 1 虚拟机配置介绍 在创建虚拟机的时候只给了20G磁盘空间大小&#xff0c;但是现在需求变更&#xff0c;想要增加到40G磁盘空间大小&#xff0c;所以需要通过两步扩容磁盘空间。 系统版本是Centos7 根目录…

掼蛋功能之识别性格篇

常说&#xff1a;千人千面。大多数人一到牌局的场面&#xff0c;往往精神便会放松&#xff0c;面貌神情不再收敛&#xff0c;一言一行体现出的性格暴露无疑&#xff0c;具体表现为以下几种&#xff1a; 1、浮躁冲动型&#xff1a;此类人多数不讲究团队配合&#xff0c;自顾自出…

了解云工作负载保护:技术和最佳实践

云工作负载是指云环境中的应用程序或存储元素&#xff0c;无论是公共云、私有云还是混合云。每个云工作负载都使用云的资源&#xff0c;包括计算、网络和存储。 云工作负载可以多种多样&#xff0c;例如运行应用程序、数据库或托管网站。它们可以是静态的或动态的&#xff0c;…

数据的跃动之美:探索ECharts动态排序柱状图的魔力

前言 在 echarts 中&#xff0c;动态排序柱状图是一种常用图表&#xff0c;可以帮助我们更好地理解数据的变化和排序规律。本文将介绍如何使用 echarts 库创建动态排序柱状图&#xff0c;以展示数据的变化趋势和排序情况。 完整代码 <template><div class"acros…

Java 数据结构集合

文章目录 Java 数据结构1. 基本数据结构1.1 数组 (Array)1.2 链表 (Linked List)1.3 栈 (Stack)1.4 队列 (Queue)双向队列优先级队列 2. 树形数据结构2.1 二叉树 (Binary Tree)2.2 堆 (Heap) 3. 散列数据结构3.1 哈希表 (Hash Map)3.2 LinkedHashMap3.3 TreeMapConcurrentHashM…

Cesium for Unity包无法加载

太上老君急急如律⚡令⚡ &#x1f959;关闭UnityHub&#x1f9c0;启动梯子&#x1f96a;cmd 启动UnityHub &#x1f959;关闭UnityHub &#x1f9c0;启动梯子 &#x1f96a;cmd 启动UnityHub 把批处理启动文件&#x1f448;中的exe的路径换成自己的安装目录&#xff01;保存…

[完美解决]Vue/React项目运行时出现this[kHandle] = new _Hash(algorithm, xofLen)

问题出现的原因 出现这个问题是node.js 的版本问题&#xff0c;因为 node.js V17开始版本中发布的是OpenSSL3.0, 而OpenSSL3.0对允许算法和密钥大小增加了严格的限制&#xff0c;可能会对生态系统造成一些影响。故此以前的项目在使用 nodejs V17以上版本后会报错。而github项目…

redis报错:WRONGTYPE Operation against a key holding the wrong kind of value

这个是在redis存取的数据时&#xff0c;存数据时的数据类型和取数据时的数据类型不一致导致的 原因分析 首先需要明白的是&#xff0c;出现这种错误的原因是因为我们在取值的时候&#xff0c;使用的命令不对&#xff0c;比如你用获取string类型的get命令去取列表list类…

【AI视野·今日Robot 机器人论文速览 第七十五期】Thu, 11 Jan 2024

AI视野今日CS.Robotics 机器人学论文速览 Thu, 11 Jan 2024 Totally 16 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Robotics Papers Analytical Model and Experimental Testing of the SoftFoot: an Adaptive Robot Foot for Walking over Obstacles and Irre…

山体滑坡在线监测预警系统解决方案

一、方案概述 我国是一个山区面积较大的国家&#xff0c;山地、丘陵约占国土总面积的2/3&#xff0c;在众多的山区中&#xff0c;都具备泥石流形成的基本条件&#xff0c;这也让我国成为受山体滑坡泥石流灾害影响最大的国家。山体滑坡是指山体斜坡上某一部分岩土在重力(包括岩土…

【C/C++】C/C++编程——C++ 开发环境搭建

C的开发环境种类繁多&#xff0c;以下是一些常见的C 集成开发环境&#xff1a; AppCode &#xff1a;构建与JetBrains’ IntelliJ IDEA 平台上的用于Objective-C&#xff0c;C,C&#xff0c;Java和Java开发的集成开发环境CLion&#xff1a;来自JetBrains的跨平台的C/C的集成开…

肺癌相关文献6

第十四篇 Classification of lung adenocarcinoma based on stemness scores in bulk and single cell transcriptomes IF&#xff1a;6.0 中科院分区:2区 生物学WOS分区&#xff1a;Q1被引次数&#xff1a; 4 背景&#xff1a;癌细胞具有无限期自我更新和增殖的能力[2]。在一…

解决撸卡、撸货、采退成功率低的原因和方法

在亚马逊和沃尔玛等平台上&#xff0c;不论是进行测评、撸卡还是撸货&#xff0c;确保环境的安全性和稳定性是首要任务。一个稳定的环境是进行这些项目的基础&#xff0c;如果无法解决安全性问题&#xff0c;那么进行这些项目就毫无意义。我们团队经过八、九年的环境技术研发&a…

解锁无限可能,Roxlabs代理引领未来网络新体验

文章目录 前言网络隐匿利器&#xff1a;IP代理什么是Roxlabs&#xff1f;世界百花争艳&#xff0c;我独爱一枝什么是住宅IP&#xff1f;如何选择代理类型 利用IP代理进行国外数据采集实战教学附赠一个利用代理IP实现赚钱的方法总结 前言 在数字时代的今天&#xff0c;我们对于…