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

python-leetcode 31.K个一组翻转链表

题目:

给定链表的头节点head,每K个节点一组进行翻转,返回修改后的链表。

K是正整数,它的值小于等于链表的长度,如果节点总数不是K的整数组,那么将最后剩余的节点保持原有顺序。不能只改变节点内容的值,需要进行实际的节点交换。

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

需要把链表节点按照 k 个一组分组,所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步,直至链表结尾,对于每个分组,我们先判断它的长度是否大于等于 k。若是,我们就翻转这部分链表,否则不需要翻转。

接下来的问题就是如何翻转一个分组内的子链表,

翻转一个链表并不难,过程可以参考「206. 反转链表」。但是对于一个子链表,除了翻转其本身之外,还需要将子链表的头部与上一个子链表连接,以及子链表的尾部与下一个子链表连接。

在翻转子链表的时候,我们不仅需要子链表头节点 head,还需要有 head 的上一个节点 pre,以便翻转完后把子链表再接回 pre

对于第一个子链表,它的头节点 head 前面是没有节点 pre 的,们新建一个节点,把它接到链表的头部,让它作为 pre 的初始值,这样 head 前面就有了一个节点,我们就可以避开链表头部的边界条件。

反复移动指针 head 与 pre,对 head 所指向的子链表进行翻转,直到结尾。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def reverseKGroup(self, head, k):""":type head: Optional[ListNode]:type k: int:rtype: Optional[ListNode]"""n=0  #n 用来记录链表的总节点数cur=head  #是当前指向链表的指针,从头节点开始遍历while cur:n+=1cur=cur.next    p=dummy=ListNode(next=head) #虚拟的头节点,指向原链表的头节点#p 是用来保持链表头部的指针,在每次反转一组节点后,用它来调整前一个分组的 next 指针pre=None #用来指向当前反转过程中的前一个节点cur=head #指向链表的第一个节点,作为反转操作的当前节点while n>=k: #只有当剩余的节点数大于或等于 k 时,才进行反转操作n-=k  #表示已经反转了一个大小为 k 的节点组,所以剩余的节点数减少了 kfor _ in range(k): #反转当前组的 k 个节点nxt=cur.next  #保存当前节点的下一个节点cur.next=pre #将当前节点的 next 指向前一个节点,实现反转操作pre=cur  # 将 pre 指向当前节点,作为下一个节点的前驱cur=nxt #将 cur 移动到下一个节点,继续进行反转tail=p.next #获取当前节点组反转后的尾节点tail.next=cur#将反转后的组尾节点的 next 指向当前的 cur,即未反转部分的开始p.next=pre #将p的 next 指向反转后的第一个节点,这样前一个部分和当前部分就连接在一起p=tail #更新 p0 为反转后的组的尾节点,以便处理下一个组return dummy.next

时间复杂度:O(N)

空间复杂度:O(1)

                                                                                                                              源自力扣官方题解

相关文章:

python-leetcode 31.K个一组翻转链表

题目: 给定链表的头节点head,每K个节点一组进行翻转,返回修改后的链表。 K是正整数,它的值小于等于链表的长度,如果节点总数不是K的整数组,那么将最后剩余的节点保持原有顺序。不能只改变节点内容的值,需…...

算法08-递归调用转为循环的通用方法

前导:问题引入 在Python中,递归调用过多会导致“递归深度过深”的错误,通常是因为递归没有正确终止条件或者递归层次太深。 这种错误通常会导致程序抛出 RecursionError 异常。 Python默认的递归深度限制大约是1000层(可以通过sys.getrecursionlimit()查看)。 修正方式…...

[创业之路-300]:进一步理解货币与金钱, 货币与货币政策

目录 一、货币 1.1 概述 1、货币的定义 2、货币的形态演变 3、货币的职能 4、货币的价值衡量 1.2 货币的分层 1、货币分层的目的与意义 2、货币分层的划分标准与层次 3、各国货币分层的实践 4、货币分层的影响与应用 1.3、M0、M1、M2变化对股市的影响 1、M0变化对…...

达梦:跟踪日志诊断

目录标题 参考连接**性能诊断:跟踪日志诊断****总结** 参考连接 性能诊断 -> 跟踪日志诊断 性能诊断:跟踪日志诊断 备份现有的日志配置文件 在修改文件之前,建议先备份原始文件,以防万一需要恢复。 cp /opt/dmdbms/dmdata/DA…...

Qwen2-VL 的重大省级,Qwen 发布新旗舰视觉语言模型 Qwen2.5-VL

Qwen2.5-VL 是 Qwen 的新旗舰视觉语言模型,也是上一代 Qwen2-VL 的重大飞跃。 Qwen2.5-VL主要特点 视觉理解事物:Qwen2.5-VL不仅能够熟练识别花、鸟、鱼、昆虫等常见物体,而且还能够分析图像中的文本、图表、图标、图形和布局。 代理性&…...

js考核第三题

题三:随机点名 要求: 分为上下两个部分,上方为显示区域,下方为控制区域。显示区域显示五十位群成员的学号和姓名,控制区域由开始和结束两个按钮 组成。点击开始按钮,显示区域里的内容开始滚动,…...

LabVIEW袜品压力测试系统

开发了一种基于LabVIEW开发的袜品压力测试系统。该系统利用LabVIEW并结合灵敏的传感器和高精度的处理模块,实现了对袜品压力的精确测量和分析。系统不同于传统的服装压力测试方法,为研究和评价袜子的舒适性提供了新的测试手段。 ​ 项目背景 该系统的…...

jsp页面跳转失败

今天解决一下jsp页面跳转失败的问题 在JavaWeb的学习过程中&#xff0c;编写了这样一段代码&#xff1a; <html> <body> <h2>Hello World!</h2><%--这里提交的路径&#xff0c;需要寻找到项目的路径--%> <%--${pageContext.request.context…...

1.推荐算法基本概念

推荐算法是一个非常重要且广泛应用的领域&#xff0c;特别是在电子商务、社交媒体、内容推荐等领域。第一课我们将介绍推荐算法的基本概念和分类&#xff0c;并简单讲解两种常见的推荐算法&#xff1a;协同过滤和基于内容的推荐。 推荐算法的基本概念 推荐系统的目标是根据用…...

Java 大视界 -- 大数据伦理与法律:Java 技术在合规中的作用与挑战(87)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…...

【ISO 14229-1:2023 UDS诊断全量测试用例清单系列:第十五节】

ISO 14229-1:2023 UDS诊断服务测试用例全解析&#xff08;RoutineControl_0x31服务&#xff09; 作者&#xff1a;车端域控测试工程师 更新日期&#xff1a;2025年02月14日 关键词&#xff1a;UDS协议、0x31服务、例程控制、ISO 14229-1:2023、ECU测试 一、服务功能概述 0x31服…...

【深度强化学习】策略梯度算法:REINFORCE

策略梯度 强化学习算法进阶 Q-learning、DQN 及 DQN 改进算法都是基于价值&#xff08;value-based&#xff09;的方法&#xff0c;其中 Q-learning 是处理有限状态的算法&#xff0c;而 DQN 可以用来解决连续状态的问题。在强化学习中&#xff0c;除了基于值函数的方法&#…...

手机用流量怎样设置代理ip?

互联网各领域资料分享专区(不定期更新)&#xff1a; Sheet...

CI/CD部署打包方法

项目目前部署方式&#xff1a; 各地区服务器打包同一个runner&#xff08;需要互相排队&#xff0c;不并发&#xff09;各地区客户端可以并发打包&#xff0c;同个地区客户端打多个包需要排队 部署方法 下载gitlab-runner&#xff1a; https://docs.gitlab.com/runner/insta…...

LabVIEW 中dde.llbDDE 通信功能

在 LabVIEW 功能体系中&#xff0c;位于 C:\Program Files (x86)\National Instruments\LabVIEW 2019\vi.lib\Platform\dde.llb 的 dde.llb 库占据着重要的地位。作为一个与动态数据交换&#xff08;DDE&#xff09;紧密相关的库文件&#xff0c;它为 LabVIEW 用户提供了与其他…...

探索后端开发中的异步API:基于Resilience4j与Reactive Programming的高性能设计

引言 随着微服务架构的普及&#xff0c;后端系统面临的挑战愈发严峻&#xff0c;尤其是在高并发和高可用性方面。传统的同步调用模式虽然简单&#xff0c;但在处理大量并发请求时可能会成为瓶颈。为了应对这一问题&#xff0c;异步编程逐渐成为后端开发的热门话题。 在本文中…...

leetcode 2915. 和为目标值的最长子序列的长度

题目如下 数据范围 本题就是典型的背包问题target就是容量&#xff0c;nums[i]就是第i个物品的重量。其实就是选最多的物品使得背包刚好装满。 令f(i,j)为当考虑到i - 1物品时刚好装到j重量的物品数。 当j > nums[j]时 有f(i,j) max(f(i - 1,j - nums[i - 1]) 1,f(i -…...

【Vue】打包vue3+vite项目发布到github page的完整过程

文章目录 第一步&#xff1a;打包第二步&#xff1a;github仓库设置第三步&#xff1a;安装插件gh-pages第四步&#xff1a;两个配置第五步&#xff1a;上传github其他问题1. 路由2.待补充 参考文章&#xff1a; 环境&#xff1a; vue3vite windows11&#xff08;使用终端即可&…...

Flutter编译问题记录

问题&#xff1a; 运行出现以下报错 Launching lib/main.dart on macOS in debug mode... Warning: CocoaPods not installed. Skipping pod install. CocoaPods is a package manager for iOS or macOS platform code. Without CocoaPods, plugins will not work on iOS or …...

poetry shell - 作为插件安装和使用

安装插件 安装完 poetry&#xff0c;想进入环境&#xff0c;执行 poetry shell 后会报错&#xff0c;是因为 poetry shell 在后面的版本中&#xff0c;是作为插件&#xff0c;需要额外安装。 poetry self add poetry-plugin-shell关于 poetry-plugin-shell github : https:/…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...

SQL注入篇-sqlmap的配置和使用

在之前的皮卡丘靶场第五期SQL注入的内容中我们谈到了sqlmap&#xff0c;但是由于很多朋友看不了解命令行格式&#xff0c;所以是纯手动获取数据库信息的 接下来我们就用sqlmap来进行皮卡丘靶场的sql注入学习&#xff0c;链接&#xff1a;https://wwhc.lanzoue.com/ifJY32ybh6vc…...

精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑

精益数据分析&#xff08;98/126&#xff09;&#xff1a;电商转化率优化与网站性能的底层逻辑 在电子商务领域&#xff0c;转化率与网站性能是决定商业成败的核心指标。今天&#xff0c;我们将深入解析不同类型电商平台的转化率基准&#xff0c;探讨页面加载速度对用户行为的…...