当前位置：首页 > news >正文

【LeetCode 热题100】 234. 回文链表的算法思路及python代码

news 来源：原创 2025/8/7 9:03:47

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

在这里插入图片描述

示例 2：

输入：head = [1,2]
输出：false

在这里插入图片描述

算法思路

通过 快慢指针分割链表 + 反转后半链表 的方法判断链表是否为回文。核心思想是将链表分为前后两半，反转后半部分后与前半部分逐一比较，最后恢复链表结构。具体步骤如下：

分割链表： 使用快慢指针找到前半部分的尾节点，将链表分为前后两段。
反转后半链表： 将后半部分链表反转，便于顺序比较。
比较节点值： 同时遍历前半部分和后半部分，逐一比较节点值是否相等。
恢复链表（可选）：将后半部分再次反转还原，恢复链表原始结构。

步骤详解

快慢指针分割链表：
- 快指针每次移动两步，慢指针每次移动一步。
- 当快指针到达链表末尾时，慢指针恰好指向前半部分的尾节点。
- 示例：链表 1->2->2->1，慢指针停在第二个节点 2，分割为前 1->2 和后 2->1。
反转后半部分链表：
- 通过迭代法反转后半部分链表。例如，2->1 反转为 1->2。
比较节点值：
- 从头部和反转后的后半部分头部开始遍历，比较每个节点的值。
- 示例：比较 1->2 和 1->2，发现所有节点值相等，返回 True。
恢复链表结构：
- 再次反转后半部分链表并拼接回前半部分，保持链表原始结构。

关键点

快慢指针的正确性： 确保分割点准确，无论链表长度为奇数或偶数。
反转链表的实现： 通过迭代法正确反转后半部分链表。
比较逻辑： 仅需比较前半部分和反转后的后半部分，忽略中间节点（奇数长度时）。
空间优化： 全程仅使用指针变量，空间复杂度为 O(1)。

复杂度分析

时间复杂度： $O (n)$

分割链表： $O (n /2)$
反转链表： $O (n /2)$
比较节点值： $O (n /2)$
恢复链表： $O (n /2)$
总体时间复杂度为线性 $O (n)$ 。

空间复杂度： $O (1)$

仅使用常数级别的额外空间（指针变量）。

算法代码

class Solution:def isPalindrome(self, head: ListNode) -> bool:if head is None:return True# 找到前半部分链表的尾节点并反转后半部分链表first_half_end = self.end_of_first_half(head)second_half_start = self.reverse_list(first_half_end.next)# 判断是否回文result = Truefirst_position = headsecond_position = second_half_startwhile result and second_position is not None:if first_position.val != second_position.val:result = Falsefirst_position = first_position.nextsecond_position = second_position.next# 还原链表并返回结果first_half_end.next = self.reverse_list(second_half_start)return result    def end_of_first_half(self, head):fast = headslow = headwhile fast.next and fast.next.next:fast = fast.next.nextslow = slow.nextreturn slowdef reverse_list(self, head):previous = Nonecurrent = headwhile current is not None:next_node = current.nextcurrent.next = previousprevious = currentcurrent = next_nodereturn previous

在这里插入图片描述

【LeetCode 热题100】 234. 回文链表的算法思路及python代码

234. 回文链表给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false 。示例 1： 输入：head [1,2,2,1] 输出：true示例 2： 输入&…...

编程日记 2025/8/7 9:03:47

Grid布局示例代码

示例一 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Grid Layout Example</title><styl…...

编程日记 2025/8/4 12:10:48

【K8S】ImagePullBackOff状态问题排查。

ImagePullBackOff 是在使用 Kubernetes（K8s）时经常遇到的一种错误状态，下面为你详细介绍其含义、可能的原因及解决办法。含义当你在 K8s 集群中创建一个 Pod 时，Kubelet 会尝试从指定的镜像仓库拉取所需的容器镜像。如果拉取镜…...

编程日记 2025/8/6 5:11:11

在 Kubernetes（k8s）部署过程中常见的问题

在 Kubernetes（k8s）部署过程中，常见的问题主要包括以下几类，以下是具体示例及简要说明： 1. 资源配额不足（Resource Quota）现象：Pod 处于 Pending 状态，事件日志显示 Insufficient CPU/Memory。原因：节点（Node）资源不足，无法满足 Pod 的 requests 或 limits。命…...

编程日记 2025/8/6 13:22:18

微信小程序状态管理与计算属性同时使用：miniprogram-computed 和 mobx-miniprogram

两个框架扩展提供的 ComponentWithStore 与 ComponentWithComputed 方法无法结合使用。如果需要在一个组件中既想使用 mobx-miniprogram-bindings 又想使用 miniprogram-computed解决方案是： 使用旧版 API 自定义组件仍然使用 Component 方法构建组件，将…...

编程日记 2025/8/3 16:41:35

Redis设置开机自启报错start-limit-hit

Redis设置开机自启报错start-limit-hit 问题：在银河麒麟服务器上编译安装了redis后设置systemctl开机自启报错start-limit-hit 如何解决？ 因为开机自启的需求是后面新增的，所以一开始使用的是命令启动，使用命令启动就会直接在前台…...

编程日记 2025/8/7 8:58:43

[数据结构]排序之归并排序（有详细的递归图解）

一、非递归基本思想： 归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列&#x…...

编程日记 2025/8/4 13:07:44

pdf文件分页按需查看

pdf预览本来打算粗暴点，一次性查看全部，但是一个pdf四五百页导致手机端查看超出内存直接崩掉，崩掉会导致页面疯狂刷新，所以不得不进行优化解决思路大致如下： canvas转为blob格式以图片的形式加载在页面（B…...

编程日记 2025/8/7 9:02:47

栈/堆/static/虚表

在 C 里，栈空间主要用来存放局部变量、函数调用信息等。下面为你介绍栈空间在 C 里的运用方式。 1. 局部变量的使用在函数内部定义的变量会被存于栈空间，当函数执行结束，这些变量会自动被销毁。 #include <iostream>void exampleFu…...

编程日记 2025/8/7 8:58:44

计算机网络技术服务管理基于Spring Boot-SSM

目录一、引言二、用户需求分析三、功能介绍 ‌‌3.1.资源管理‌： ‌3.2.故障管理‌： ‌3.3.性能管理‌： ‌3.4.安全管理‌： ‌3.5.配置管理‌： ‌3.6.日志管理‌： ‌3.7.用户管理‌&#xff1…...

编程日记 2025/8/7 9:00:50

Redisson 分布式锁原理

加锁原理 # 如果锁不存在 if (redis.call(exists, KEYS[1]) 0) then# hash结构,锁名称为key,线程唯一标识为itemKey，itemValue为一个计数器。支持相同客户端线程可重入,每次加锁计数器1.redis.call(hincrby, KEYS[1], ARGV[2], 1);# 设置过期时间redis.call(pexpi…...

编程日记 2025/8/5 11:35:05

LLM(5)：了解 GPT 架构

1.6 对 GPT 架构的更深入了解 GPT 最初由 OpenAI 的 Radford 等人在论文《通过生成式预训练提高语言理解能力》中提出。GPT-3 是该模型的扩展版本，具有更多的参数，并且使用了更大的数据集进行训练。此外，ChatGPT 中提供的原始模型是通过在大…...

编程日记 2025/8/6 9:12:40

Android Zygote 启动流程梳理

和你一起终身学习，这里是程序员Android 本篇文章主要介绍 Android Zygote 启动分析知识点，通过阅读本篇文章，您将收获以下内容: 一、Android 系统基本服务二、虚拟机创建和第一个Java 程序引导三、Dalvik 虚拟机基本配置四、Zygote 启动流程…...

编程日记 2025/7/27 1:47:49

华为OD机试-绘图机器-双指针（Java 2025 A卷 100分）

题目描述绘图机器的绘图笔初始位置在原点 (0, 0)。机器启动后按照以下规则绘制直线：尝试沿着横坐标正向绘制直线，直到给定的终点 E。期间可以通过指令在纵坐标轴方向进行偏移，offsetY 为正数表示正向偏移，为负数表示负向偏移。给定的横坐标终点值 E 以及若干条绘制指令，…...

编程日记 2025/8/5 7:08:02

ESP32（1）基于ESP32的lwIP了解

ESP32-S3 是一款集成了 Wi-Fi 和蓝牙功能的微控制器，而 lwIP（轻量级 IP）是一个为嵌入式系统设计的开源 TCP/IP 协议栈。通过使用 lwIP 库， ESP32-S3 可以实现与外部网络的通信，包括发送和接收数据包、处理网络连接等。…...

编程日记 2025/8/7 9:03:45

C语言预处理详解

目录 （一）预处理符号 （二）define定义常量和宏 （三）#符号和##符号 （四）undef符号的条件编译 （五）头文件的包括 （一）预处理符号在…...

编程日记 2025/7/31 7:59:00

python实现接口自动化

代码实现自动化相关理论代码编写脚本和工具实现脚本区别是啥? 代码： 优点：代码灵活方便缺点：学习成本高工具： 优点：易上手缺点：灵活度低，有局限性。总结： 功能脚本：工…...

编程日记 2025/8/3 10:07:32

当Anaconda的安装路径与我想创建的conda虚拟环境路径不一致时，应该怎么操作？

我的anaconda安装在该路径：D:\Program\anaconda3 , 如果我想在F盘创建一个虚拟环境应该怎么做呢？ 若你想在 F 盘创建 Anaconda 虚拟环境，可使用 conda create 命令，并通过 --prefix 参数指定环境路径。以下是详细步骤&#xff1…...

编程日记 2025/8/5 5:09:55

MongoDB慢日志查询及索引创建

MongoDB 的慢日志（Slow Query Log）对于运维和程序员来说都非常重要，因为它直接关系到数据库的性能和应用程序的稳定性。以下分享介绍下MongoDB慢日志查询及索引创建相关的一些笔记。一，准备 1. 使用 db.currentOp() 实时监控 …...

编程日记 2025/7/31 4:24:24

C语言指针（详细总结）

目录 1.初始C指针几个重要的概念： 指针的加减 &与* 二级指针 2.指针与数组指针数组数组指针变量一维数组与二维数组传参的本质编辑编辑编辑 3.指针与函数函数指针数组 4.指针与结构体 5.野指针以及常见的内存管理错误常见的内存错…...

编程日记 2025/8/7 9:02:11

服务器部署Kong和Konga过程

前言最近在想怎么将一个接口给外部提供服务，并且可以根据和对放的关系，设置不同的期限或者服务大小？并且有友好的可视化页面！这让我了解到了 API 网关，所以我开始研究 Kong 和 Konga 的使用。实际上我最开始研究的apisix，但是部署了好久因为etcd不支持 http 无法连接…...

编程日记 2025/8/4 1:06:24

stm32第五天按键的基础知识

一：按键连接示意图按键控制LED灯软件设计流程初始化系统 o 初始化GPIO外设时钟 o 初始化按键和LED的引脚 • 检测按键输入电平来控制LED灯 o SW2控制灯开。 SW3控制灯关 1：key.c工程 #include"key.h" #include"stm32f10x.h"v…...

编程日记 2025/8/7 9:00:48

高主频CPU+RTX4090：AI生图性能优化超150%

概述：消费级高主频CPU搭配 RTX 4090显卡可以显著提高AI生图的性能，相比于企业级CPU具有更大的吞吐量和更优的成本效益。引言：在AI图像生成过程中，CPU与GPU的协同效应对系统的整体性能至关重要。测试表明，与RTX 4090显…...

编程日记 2025/8/4 22:55:53

自学Python创建强大AI：从入门到实现DeepSeek级别的AI

人工智能（AI）是当今科技领域最热门的方向之一，而Python是AI开发的首选语言。无论是机器学习、深度学习还是自然语言处理，Python都提供了丰富的库和工具。如果你梦想创建一个像DeepSeek这样强大的AI系统，本文将为你提供…...

编程日记 2025/7/30 8:19:47

主流区块链

文章目录主流链1. Solana特点：适用场景：工具链： 2. Binance Smart Chain (BSC)特点：适用场景：工具链： 3. Avalanche特点：适用场景：工具链： 4. Polkadot特点：…...

编程日记 2025/8/4 8:05:47

DevEco Studio的使用

目录 1.创建ArkTS工程 2.ArkTS工程目录结构（Stage模型） 构建第一个页面构建第二个页面实现页面间的跳转 1.创建ArkTS工程若首次打开DevEco Studio，请点击Create Project创建工程。如果已经打开了一个工程，请在菜单栏选择…...

编程日记 2025/7/31 21:37:00

Oracle 公布 Java 的五大新功能

Java 增强提案包括语言增强和性能优化，从 JDK 25 中的稳定值 API 开始。随着JDK（Java 开发工具包）24刚刚全面上市，Oracle 提前透露了不久的将来即将推出的 Java 功能，包括增强原始装箱到空限制值类类型。 3 月 18 日…...

编程日记 2025/8/6 9:15:18

checkpoint机制

1、什么是checkpoint 将缓冲池中的脏页刷新到磁盘，并更新redo log的checkpoint位点，确保数据库在发生故障时可以快速恢复到一致的状态。 2、checkpoint执行过程确保需要刷新的脏页：从缓冲池中选取一部分需要刷新的页数据页刷新&#xff1…...

编程日记 2025/8/6 8:27:50

MySQL函数大全（持续更新）

MySQL常用函数一、字符串函数函数功能 CONCAT(s1, s2, ...) 拼接字符串 CONCAT_WS(sep, s1, s2, ...) 指定分隔符拼接字符串 SUBSTRING(str, start, length) 截取字符串 LEFT(str, length) 从左边截取指定长度字符串 RIGHT(str, length) 从右边截取指定长度字符串 LENGTH(s…...

编程日记 2025/8/7 6:30:14

商业智能BI分析中，汽车4S销售行业的返厂频次有什么分析价值？

买过车的朋友会发现，同一款车不管在哪个4S店去买，基本上价格都相差不大。即使有些差别，也是带着附加条件的，比如要做些加装需要额外再付一下费用。为什么汽车4S销售行业需要商业智能BI？就是因为在汽车4S销售行业&#…...

编程日记 2025/8/5 17:35:29

51单片机程序变量作用域问题

问题： //为什么下面这个程序可以运行 #include <REGX52.H> #include "LCD1602.h" #include "Delay.h" unsigned int result 0; void main(){LCD_Init();while(1){LCD_ShowNum(1,1,result,3);Delay(200);result;}; } //但是这样会报错&a…...

编程日记 2025/8/3 17:16:56

力扣算法ing(33 / 100)

3.20 146.LRU缓存请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类： LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值&…...

编程日记 2025/8/2 16:08:05

基于springboot的母婴商城系统（018）

摘要现代经济快节奏发展以及不断完善升级的信息化技术，让传统数据信息的管理升级为软件存储，归纳，集中处理数据信息的管理方式。本母婴商城系统就是在这样的大环境下诞生，其可以帮助管理者在短时间内处理完毕庞大的数据信息&am…...

编程日记 2025/8/5 19:39:02

【数学建模】模糊综合评价模型详解、模糊集合论简介

模糊综合评价模型详解文章目录模糊综合评价模型详解1. 模糊综合评价模型概述2. 模糊综合评价的基本原理2.1 基本概念2.2 评价步骤 3. 模糊综合评价的数学模型3.1 数学表达3.2 模糊合成运算 4. 模糊综合评价的应用领域5. 模糊综合评价的优缺点5.1 优点5.2 缺点 6. 模糊综合评价…...

编程日记 2025/8/4 19:52:42

BSCAN2-1：load design

1. DFT Flow Using Tessent Shell Tessent BoundaryScan 具有一个基本的高层次流程顺序。下图展示了将 Tessent BoundaryScan 插入设计所需的高层次步骤顺序。图中的每个步骤都链接到有关可测试性设计（DFT）流程的更详细信息，包括示例。 Desi…...

编程日记 2025/8/2 16:17:58

Pytorch中layernorm实现详解

平时我们在编写神经网络时，经常会用到layernorm这个函数来加快网络的收敛速度。那layernorm到底在哪个维度上进行归一化的呢？ 一、问题描述首先借用知乎上的一张图，原文写的也非常好，大家有空可以去阅读一下，链接放…...

编程日记 2025/8/6 6:05:56

Redis HyperLogLog

Redis HyperLogLog HyperLogLog 是 Redis 提供的一种基数估算（Cardinality Estimation）数据结构，专门用于统计去重元素的数量（近似值）。 1. HyperLogLog 特点 ✅ 节省内存：无论存储的元素有 10 个还是 …...

编程日记 2025/8/4 16:48:11

【微服务日志收集①】使用FileBeat+Logstash+ES搭建ELK日志系统

使用FileBeatLogstashES搭建ELK日志系统，架构图如下： 1、使用docker快速创建ES服务和Kibana服务前置条件：需要在linux上提前安装好docker和docker-compose 1.1、在linux创建好一个用于存放docker-compose配置文件的文件夹我的目录是/app/…...

编程日记 2025/8/5 1:37:25

【FAQ】HarmonyOS SDK 闭源开放能力 —Push Kit（10）

1.问题描述： 离线推送，锁屏的时候没有弹出消息，只有下拉在通知中心里面显示。请问是否是正常的？ 解决方案： 检查一下是否存在图片风控：https://developer.huawei.com/consumer/cn/doc/harmonyos-referen…...

编程日记 2025/8/4 22:07:19

1、确保app已配置完(settings.py文件里面配置） INSTALLED_APPS [django.contrib.admin,django.contrib.auth,django.contrib.contenttypes,django.contrib.sessions,django.contrib.messages,django.contrib.staticfiles,app.apps.AppConfig #配置已经注册好的app…...

编程日记 2025/8/3 5:23:16

Redis Sentinel（哨兵模式）高可用性解决方案

一、概述 Redis Sentinel（哨兵模式）是Redis的高可用性（High Availability, HA）解决方案，它通过哨兵系统和Redis实例的协同工作，确保了Redis服务的高可用性和数据的持久性。哨兵系统由一个或多个哨兵进程组…...

编程日记 2025/8/6 20:44:52

Redis缓存与数据库数据一致性保障

为什么要保证数据一致性只要使用redis做缓存，就必然存在缓存和DB数据一致性问题。若数据不一致，则业务应用从缓存读取的数据就不是最新数据，可能导致严重错误。比如将商品的库存缓存在Redis，若库存数量不对，则下单时…...

编程日记 2025/8/6 23:36:15

Grid 布局实现三栏布局

使用 CSS Grid 布局实现三栏布局（左右固定 100px，中间自适应）的核心原理是通过网格模板精确控制列宽分配。以下是具体实现方法及优化技巧：一、基础实现父容器设置为外层容器添加 display: grid 使其成为网格容器，并通过 grid-template-columns 定义列宽 css .contain…...

编程日记 2025/8/4 10:36:17

如何在 HTML 中创建一个有序列表和无序列表，它们的语义有何不同？

大白话如何在 HTML 中创建一个有序列表和无序列表，它们的语义有何不同？ 1. HTML 中有序列表和无序列表的基本概念在 HTML 里，列表是一种用来组织信息的方式。有序列表就是带有编号的列表，它可以让内容按照一定的顺序呈现&#…...

编程日记 2025/6/28 2:31:13

springboot第三站（1） web开发引入

目录 1.简介 2.SpringBoot对静态资源的映射规则 3.模版引擎 1.简介使用SpringBoot； 1）、创建SpringBoot应用，选中我们需要的模块； 2）、SpringBoot已经默认将这些场景配置好了，只需要在配置文件中指定…...

编程日记 2025/8/5 4:42:09

nginx 简单实践：负载均衡【nginx 实践系列之四】

〇、前言本文为 nginx 简单实践系列文章之三，主要简单实践了负载均衡，仅供参考。注意：可以使用测试域名，但前提是要修改 hosts 文件路径和重启：Linux（/etc/hosts）（重启命令&#…...

编程日记 2025/8/3 23:41:05

CentOS 7.9 安装 Python 3.10 详细步骤及常见问题解决

一、环境准备与依赖安装更新系统与开发工具 sudo yum update -y sudo yum groupinstall "Development Tools" -y sudo yum install -y zlib-devel bzip2-devel openssl-devel ncurses-devel sqlite-devel \ readline-devel tk-devel libffi-devel gdbm-devel db4-de…...

编程日记 2025/8/6 7:55:47

计算机网络-1-1计算机网络体系结构

第一章计算机网络体系结构绪论《计算机网络》学什么？——数据如何通过网络正确、可靠地从A传送到B 【考纲内容】 (一)计算机网络概述计算机网络的概念、组成与功能；计算机网络的分类； 计算机网络的性能指标 (二)计算机网…...

编程日记 2025/8/3 0:01:35

集装箱箱号OCR识别技术，在铁路物流场站集装箱装卸机械数字化系统中的应用

集装箱装卸机械数字化是针对铁路物流场站的门式起重机、集装箱正面吊运起重机、重型叉车、堆高机等作业设备，在不影响原设备作业性能情况下，通过增加或集成集装箱箱号OCR识别或者车号识别装置、北斗定位装置、PLC采集装置等，利用多种通信协议…...

编程日记 2025/8/4 23:30:36

数仓工具—Hive语法之不同纬度聚合

不同纬度聚合提到不同纬度聚合，大家想到的肯定是grouping sets，或者是cube和rollup 其实这些我们之前都讲过，可以看看之前的文章数仓工具—Hive语法之cube和rollup 数仓工具—Hive语法之grouping sets 但是我们今天遇到的问题是，使用的工具不支持grouping sets，既然…...

编程日记 2025/8/4 22:29:46

234. 回文链表

示例 1：

示例 2：

算法思路

步骤详解

关键点

复杂度分析

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( 1 ) O(1) O(1)

算法代码

相关文章：

时间复杂度： $O (n)$

空间复杂度： $O (1)$