K 个一组反转链表
力扣第 25 题:K 个一组反转链表
题目描述
给定一个链表,将链表每k个节点一组进行反转,并返回修改后的链表。如果最后一组节点数少于 k,则保持原顺序。
- 示例 1:
- 输入:
1 -> 2 -> 3 -> 4 -> 5,K = 2 - 输出:
2 -> 1 -> 4 -> 3 -> 5
- 输入:
- 示例 2:
- 输入:
1 -> 2 -> 3 -> 4 -> 5,K = 3 - 输出:
3 -> 2 -> 1 -> 4 -> 5
- 输入:
解题思路
- 创建哑节点
dummy,使dummy->next = head,便于链表处理。 - 使用两个指针
prev和end分别标记每组要反转的起始和结束位置。 - 遍历链表,将每组长度为
K的节点反转;若不足K个则保持原顺序。 - 在反转过程中,断开当前节点的
next指针,保证节点反转后的正确链接。 - 重复以上过程直到链表尾部。
代码实现
#include <stdio.h>
#include <stdlib.h>// 定义链表节点
struct ListNode {int val;struct ListNode *next;
};// 创建新节点
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}// 反转链表
struct ListNode* reverse(struct ListNode* head, struct ListNode* tail) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr != tail) {struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}// K 个一组反转链表
struct ListNode* reverseKGroup(struct ListNode* head, int k) {if (k <= 1 || head == NULL) return head;// 创建哑节点struct ListNode* dummy = createNode(0);dummy->next = head;struct ListNode* prev = dummy;struct ListNode* end = head;while (end != NULL) {// 将 end 指针移动到第 k 个节点for (int i = 1; i < k && end != NULL; i++) {end = end->next;}if (end == NULL) break; // 节点不足 k 个,跳出循环struct ListNode* nextGroup = end->next;struct ListNode* start = prev->next;// 断开链表,反转当前组end->next = NULL;prev->next = reverse(start, end->next);// 将反转后的链表重新连接到下一组start->next = nextGroup;// 移动 prev 和 end 到下一组起点prev = start;end = prev->next;}struct ListNode* newHead = dummy->next;free(dummy);return newHead;
}// 打印链表
void printList(struct ListNode* head) {while (head != NULL) {printf("%d -> ", head->val);head = head->next;}printf("NULL\n");
}// 主函数测试
int main() {// 创建链表:1 -> 2 -> 3 -> 4 -> 5struct ListNode* head = createNode(1);head->next = createNode(2);head->next->next = createNode(3);head->next->next->next = createNode(4);head->next->next->next->next = createNode(5);printf("原链表: ");printList(head);// K 个一组反转int k = 3;struct ListNode* newHead = reverseKGroup(head, k);printf("K = %d 时的反转链表: ", k);printList(newHead);return 0;
}
代码详解
1. reverse 函数
reverse 函数负责反转指定部分链表,head 表示要反转的起始节点,tail 表示结束节点。反转后,prev 指向反转后的链表开头。
2. reverseKGroup 函数
根据 k 的值分组反转链表,若最后一组节点数量不足 k 则保持原顺序。
- prev:记录每组的前一位置,便于反转后重新连接。
- end:每次向后移动到第
k个节点,确定反转的终止位置。 - nextGroup:保存下一组节点起始位置。
图解流程
以链表 1 -> 2 -> 3 -> 4 -> 5、k = 3 为例,代码运行流程如下:
-
初始链表:
1 -> 2 -> 3 -> 4 -> 5 -
第一轮反转:
- 选择前
3个节点,反转后链表变为:
3 -> 2 -> 1 -> 4 -> 5 - 选择前
-
剩余节点不足
k个:- 保持原顺序,退出循环。
最终结果为 3 -> 2 -> 1 -> 4 -> 5。
相关文章:
K 个一组反转链表
力扣第 25 题:K 个一组反转链表 题目描述 给定一个链表,将链表每k个节点一组进行反转,并返回修改后的链表。如果最后一组节点数少于 k,则保持原顺序。 示例 1: 输入:1 -> 2 -> 3 -> 4 -> 5&…...
#深度学习:从基础到实践
深度学习是人工智能领域近年来最为火热的技术之一。它通过构建由多个隐藏层组成的神经网络模型,能够从海量数据中自动学习特征和表征,在图像识别、自然语言处理、语音识别等领域取得了突破性进展。本文将全面介绍深度学习的基础知识、主要算法和实践应用,帮助您快速…...
Android Kotlin中协程详解
博主前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住也分享一下给大家, 👉点击跳转到教程 前言 Kotlin协程介绍: Kotlin 协程是 Kotlin 语言中的一种用于处理异步编程的机制。它提供了一…...
【webpack学习】
webpack由于历史包袱导致复杂,只要把握关键流程即可 webpack的主要流程loader plugin难点:HMR / 懒加载 原理webpack 的优化手段 构建工具对比 webpack :可以打包任何资源,配置略复杂,适合项目开发rollup࿱…...
H5实现PDF文件预览,使用pdf.js-dist进行加载
H5实现PDF文件预览,使用pdf.js-dist进行加载 一、应用场景 在H5平台上预览PDF文件是在原本已经开发完成的系统中新提出的需求,原来的系统业务部门是在PC端进行PDF的预览与展示,但是现在设备进行了切换,改成了安卓一体机进行文件…...
面试域——面试系统工程
摘要 1. 当前就业面试场景 1.1. 招聘市场的“551 定律” 你知道招聘市场的“551 定律”吗? 551 定律:每一层筛选环节都会有百分之十的折损率。一个岗位从接收简历到发下 Offer 至少要筛选 500 份左右的简历、面试 50 人左右、只有 5 人左右通过面试&am…...
PHP-FPM 性能配置优化
4 核 8 G 服务器大约可以开启 500 个 PHP-FPM,极限吞吐量在 580 qps (Query Per Second 每秒查询数)左右。 Nginx php-fpm 是怎么工作的? php-fpm 全称是 PHP FastCGI Process Manager 的简称,从名字可得知ÿ…...
渗透测试-百日筑基—SQL注入篇时间注入绕过HTTP数据编码绕过—下
day8-渗透测试sql注入篇&时间注入&绕过&HTTP数据编码绕过 一、时间注入 SQL注入时间注入(也称为延时注入)是SQL注入攻击的一种特殊形式,它属于盲注(Blind SQL Injection)的一种。在盲注中,攻击…...
Unity - UGUI动静分离
原理:UGUI 是基于Canvas来进行合并计算的 1.不同Cavans的UI元素,是无法合批渲染,无法实现同一个drawcall 2. 每次合批的时候,会合并计算Canvas下所有的UI元素 , 具体流程: Step1: 对Cavans下所有的UI元素进行合批计算 Step2: …...
arm 体系架构-过程调用约定
ref: ARM体系结构学习笔记:过程调用标准AAPC、 ARM32调用约定、ARM64调用约定_arm64 传参 结构体-CSDN博客 ARM软件逆向工程入门 01 - ARM调用约定(Calling Convention)_armv7函数调用约定-CSDN博客 ARM学习(17&…...
STM32基于LL库的USART+DMA使用
时隔两年半再次更新LL库,本次带来USART DMA 实现接收不定长。 1、开发思路 使用USART DMA接收不定长的功能的思路是:借助USART的空闲中断、DMA发送完成中断。 打开F103的手册可得知,USART的空闲中断触发条件是在接收完成后触发࿰…...
设计模式06-结构型模式1(适配器/桥接/组合模式/Java)
#1024程序员节|征文# 4.1 适配器模式 结构型模式(Structural Pattern)的主要目的就是将不同的类和对象组合在一起,形成更大或者更复杂的结构体。结构性模式的分类: 类结构型模式关心类的组合,由多个类…...
【损害和风险评估&坑洼】路面坑洼检测系统源码&数据集全套:改进yolo11-DCNV3
改进yolo11-DLKA等200全套创新点大全:路面坑洼检测系统源码&数据集全套 1.图片效果展示 项目来源 人工智能促进会 2024.10.24 注意:由于项目一直在更新迭代,上面“1.图片效果展示”和“2.视频效果展示”展示的系统图片或者视频可…...
GenAI 生态系统现状:不止大语言模型和向量数据库
自 20 个月前 ChatGPT 革命性的推出以来,生成式人工智能(GenAI)领域经历了显著的发展和创新。最初,大语言模型(LLMs)和向量数据库吸引了最多的关注。然而,GenAI 生态系统远不止这两个部分&#…...
gitlab 配置ssh keys
settings -- 终端配置: git config --global user.email "yxthotmail.cm" 配置gitlab 账号邮箱 git config --global user.name "xt.yao" 配置gitlab账号用户名 生成SSH key,输入命令ssh-keygen -t rsa,一直按回车…...
小程序开发实战:PDF转换为图片工具开发
目录 一、开发思路 1.1 申请微信小程序 1.2 编写后端接口 1.3 后端接口部署 1.4 微信小程序前端页面开发 1.5 运行效果 1.6 小程序部署上线 今天给大家分享小程序开发系列,PDF转换为图片工具的开发实战,感兴趣的朋友可以一起来学习一下!…...
我有两台120kw充电桩一天能赚多少钱
(当前是理想状态下,当然还要看场地费用,还有物业,变压器,等等) ———————————————————— ———————————————————— 要计算两台120kW充电桩能赚多少钱,我们…...
深入了解 Android 中的命名空间:`xmlns:tools` 和其他常见命名空间
在 Android 开发中,xmlns (.xml的namespace)命名空间是一个非常重要的概念。通过引入不同的命名空间,可以使用不同的属性来设计布局、设置工具属性或者支持自定义视图等。除了 xmlns:tools 以外,还有很多常见的命名空间…...
stable-zero123模型构建指南
一、介绍 stabilityai出品,能够对有简单背景的物体进行三维视角图片的生成,简单来说也就是通过调整变换观察的视角生成对应视角的图片。 本项目通过comfyui实现。 二、容器构建说明 1. 部署ComfyUI (1)使用命令克隆ComfyUI g…...
算法题解记录32+++最长连续序列(百题筑基)
你们好,我是蚊子码农,好久不见。由于秋招求职的繁琐事情,我有很长一段时间没更新博客,希望我的粉丝们能够谅解。 秋招我拿到了一些offer,最终决定去一个主要做“网络安全”业务的公司工作,也许明天会更好&a…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
