LeetCode-热题100:K 个一组翻转链表

题目描述

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

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:
在这里插入图片描述

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

示例 2:

在这里插入图片描述

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

提示:

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

代码及注释

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// reverseKGroup 函数用于反转链表中的每 k 个节点。
func reverseKGroup(head *ListNode, k int) *ListNode {
    // 创建一个哑节点作为链表的起始节点
    dummy := &ListNode{
        Next: head,
    }
    // 初始化 pre 节点为哑节点
    pre := dummy
    // 遍历链表,直到 head 为 nil
    for head != nil {
        // 初始化 tail 节点为 pre
        tail := pre
        // 找到需要反转的 k 个节点的尾节点
        for i := 0; i < k; i++ {
            tail = tail.Next
            // 如果剩余节点数少于 k,则直接返回结果
            if tail == nil {
                return dummy.Next
            }
        }
        // 记录下一个节点
        next := tail.Next
        // 调用 reverseAll 函数反转 k 个节点
        head, tail = reverseAll(head, tail)
        // 将反转后的链表连接到原链表中
        pre.Next = head
        tail.Next = next
        // 更新 head 和 pre
        head = tail.Next
        pre = tail
    }
    // 返回反转后的链表
    return dummy.Next
}

// reverseAll 函数用于反转从 head 到 tail 的链表
func reverseAll(head, tail *ListNode) (*ListNode, *ListNode) {
    // 初始化 pre 为 tail 的下一个节点
    pre := tail.Next
    // 初始化 cur 为 head
    cur := head
    // 遍历 head 到 tail 之间的节点,并进行反转
    for pre != tail {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    // 返回反转后的头尾节点
    return tail, head
}

代码解释

reverseKGroup 函数:
  1. 初始化哑节点和 pre 节点

    dummy := &ListNode{
        Next: head,
    }
    pre := dummy
    
    • 创建一个哑节点作为链表的起始节点,这样可以简化后续的操作。
    • 初始化 pre 节点为哑节点。
  2. 遍历链表

    for head != nil {
    
    • 使用 for 循环遍历链表,直到 headnil
  3. 找到需要反转的 k 个节点的尾节点

    tail := pre
    for i := 0; i < k; i++ {
        tail = tail.Next
        if tail == nil {
            return dummy.Next
        }
    }
    
    • 初始化 tail 节点为 pre
    • 使用 for 循环找到需要反转的 k 个节点的尾节点。
  4. 记录下一个节点和反转链表

    next := tail.Next
    head, tail = reverseAll(head, tail)
    
    • 记录 tail 的下一个节点。
    • 调用 reverseAll 函数反转 k 个节点。
  5. 连接反转后的链表到原链表中

    pre.Next = head
    tail.Next = next
    
    • 将反转后的链表连接到原链表中。
    • 更新 headpre
  6. 返回反转后的链表

    return dummy.Next
    
    • 返回反转后的链表。
reverseAll 函数:
  1. 初始化 pre 和 cur

    pre := tail.Next
    cur := head
    
    • 初始化 pretail 的下一个节点。
    • 初始化 curhead
  2. 反转链表

    for pre != tail {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    
    • 使用 for 循环遍历 headtail 之间的节点,并进行反转。
  3. 返回反转后的头尾节点

    return tail, head
    
    • 返回反转后的头尾节点。

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

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

相关文章

小白能看懂的CyberRT学习笔记

0. 简介 Apollo Cyber RT 是专为自动驾驶场景设计的开源、高性能运行时框架。 基于中心化计算模型&#xff0c;主要价值是提升自动驾驶系统的高并发、低延迟、高吞吐。 Apollo 并不是一开始就使用 CyberRT&#xff0c;在 v3.0 之前用的都是基于 ROS 框架进行开发。但在之前的…

SQL Server详细安装使用教程

1.安装环境 现阶段基本不用SQL Server数据库了&#xff0c;看到有这样的分析话题&#xff0c;就把多年前的存货发一下&#xff0c;大家也可以讨论看看&#xff0c;思路上希望还有价值。 SQL Server 2008 R2有32位版本和64位版本&#xff0c;32位版本可以安装在Windows XP及以上…

ES11 学习

文章目录 1. Promise.allSettled2. Module 新增2.1 ! 动态导入 import()2.2 import.meta2.3 export * as obj from module 3. 字符串 matchAll()4. BigInt实际开发相关使用 5. globalThis6. 空值合并运算符7. 可选链操作符 1. Promise.allSettled Promise.allSettled() 返回一个…

【算法详解】双指针

双指针 常见的双指针有两种形式&#xff0c;一种是对撞指针&#xff0c;一种是左右指针。 1. 双指针简介 双指针&#xff08;Two Pointers&#xff09;&#xff1a;指的是在遍历元素的过程中&#xff0c;不是使用单个指针进行访问&#xff0c;而是使用两个指针进行访问&#…

【uniapp】个推H5号码认证一键登录(附代码)

前言 最近在做APP、h5产品&#xff0c;登陆注册成了难题。邮箱验证多数人不会使用&#xff0c;还是短信方便点&#xff0c;短信可以采用号码认证和验证码的方式&#xff0c;前者稍微便宜的&#xff0c;关于性价比和上手程度我推荐个推&#xff0c; 于是有了今天这篇案例记录&a…

谷歌浏览器插件开发速成指南:弹窗

诸神缄默不语-个人CSDN博文目录 本文介绍谷歌浏览器插件开发的入门教程&#xff0c;阅读完本文后应该就能开发一个简单的“hello world”插件&#xff0c;效果是出现写有“Hello Extensions”的弹窗。 作为系列文章的第一篇&#xff0c;本文还希望读者阅读后能够简要了解在此基…

爬取日本常用汉字秘籍

前言 昨天投简历时遇到了这样的一个笔试。本以为会是数据结构算法之类的没想到直接发了一个word直接提需求&#xff0c;感觉挺有意思就写了这篇文章&#xff0c;感兴趣的朋友可以看看。 1. 网页内容解析 首先&#xff0c;我们通过请求网页获取到日本常用汉字的链接列表。然后…

计算机网络——38报文完整性

报文完整性 数字签名 数字签名类比于手写签名 发送方数字签署了文件&#xff0c;前提是他是文件的拥有者/创建者可验证性&#xff0c;不可伪造性&#xff0c;不可抵赖性 谁签署&#xff0c;接收方可以向他人证明是他&#xff0c;而不是其他人签署了这个文件签署了什么&#…

Web攻击越发复杂,企业如何保护云上业务

如今&#xff0c;电子政务、电子商务、网上银行、网上营业厅等依托Web应用&#xff0c;为广大用户提供灵活多样的服务。在这之中&#xff0c;流量攻击堪称是Web应用的最大敌人&#xff0c;黑客通过流量攻击获取利益、竞争对手雇佣黑客发起恶意攻击、不法分子通过流量攻击瘫痪目…

ShardingSphere-JDBC使用时出现雪花算法id无法生成

出现报错&#xff1a; 这是sql 尝试1&#xff1a; 这里改成Long 还是报错 尝试2&#xff1a;将配置重写 删除 props: # 主键生成器属性配置worker-id: 1 # Snowflake算法中的workerId配置解决&#xff01;

基于Difussion图像、视频生成综述

2024年大年初七&#xff08;02.16&#xff09;OpenAI 发布视频生成模型 Sora 在各大平台转疯了&#xff0c;和2022年发布ChatGPT3.5时一样的疯狂。在开工第一天&#xff0c;我就去官网上看了 Sora 的技术报告&#xff0c;遗憾的是&#xff0c;在这份技术报告中只披露了一些模型…

苹果证书分类及作用详解,助力开发者高效管理应用程序

转载&#xff1a;苹果证书的作用及分类详解 摘要&#xff1a;本文将详细介绍苹果证书的作用及分类&#xff0c;包括企业证书、开发者证书、 推送证书、分发证书和MDM证书&#xff0c;帮助开发者了解如何正确使用和管理这些证书&#xff0c; 提升应用程序的开发和发布效率。 引…

基于SSM的校园二手物品交易平台论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本校园二手物品交易平台就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据…

基于单片机分舱式电开水炉位控制系统

**单片机设计介绍&#xff0c;基于单片机分舱式电开水炉位控制系统 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机分舱式电开水炉位控制系统概要主要涉及通过单片机对电开水炉的各个舱位进行精确控制&#xff0c;实现水位、温度…

C++中的指针:其重要性与应用深度解析

在C编程语言的世界中&#xff0c;指针无疑是一个至关重要的概念。它不仅是C语言的核心特性之一&#xff0c;更是实现高效、灵活编程的关键工具。理解并熟练掌握指针的使用&#xff0c;对于提升程序设计能力、优化代码性能以及深入理解计算机内存模型具有不可估量的价值。 为了帮…

HarmonyOS 应用开发-ArkUI(ets)仿“腾讯新闻”APP

一、效果演示 1、新闻列表页 2、新闻详情页、图片展示页 3、视频页 4、动态页 二、 流程图 –本来自定义了视频的控制栏的&#xff0c;但是发现VideoController()控制器的bug会导致控制器失效&#xff0c;所以没继续做。视频页先不搞了。 三、文件组织&#xff08;“我的页面…

mac上搭建鸿蒙开发环境(2024)

开发环境 设备 MacBook Pro 芯片 Apple M1 系统 11.4 内存 16 GB 一、下载公开版本的DevEco Studio 华为官方目前对外提供的版本是DevEco Studio 3.1&#xff0c;可在官网下载https://developer.huawei.com/consumer/cn/deveco-studio/ 因为目前还在学习阶段&#xff0c;…

OpenHarmony实战:轻量系统STM32F407芯片移植案例

介绍基于STM32F407IGT6芯片在拓维信息Niobe407开发板上移植OpenHarmony LiteOS-M轻量系统&#xff0c;提供交通、工业领域开发板解决方案。 移植架构采用Board与SoC分离方案&#xff0c;使用arm gcc工具链Newlib C库&#xff0c;实现了lwip、littlefs、hdf等子系统及组件的适配…

循序表实战——基于循序表的通讯录

前言&#xff1a;本篇文章主要是利用顺序表作为底层&#xff0c; 实现一个通讯录。偏向于应用&#xff0c; 对于已经学习过c的友友们可能没有难度了已经。没有学习过c的友友&#xff0c; 如果顺序表不会写&#xff0c; 或者说没有自己实现过&#xff0c; 请移步学习顺序表相关内…

xgo: golang基于-toolexec实现猴子补丁

注&#xff1a; 转载请注明出处&#xff0c; 原文链接。 概述 在这篇博客中&#xff0c;我将详细介绍 xgo 的实现细节。 如果你不知道&#xff0c;xgo 项目位于 https://github.com/xhd2015/xgo。 它的作用很简单&#xff0c;就是在每个 Go 函数的开头添加拦截器&#xff0…