Leetcode25. K个一组翻转链表
创始人
2024-06-02 18:24:59
0

目录

    • 一、题目描述:
    • 二、解决思路和代码
      • 1. 解决思路
      • 2. 代码

一、题目描述:

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

  1. 示例 1:
    • 输入:head = [1,2,3,4]
    • 输出:[2,1,4,3]
  2. 示例 2:
    • 输入:head = []
    • 输出:[]
  3. 示例 3:
    • 输入:head = [1]
    • 输出:[1]
  • 提示:
    • 链表中节点的数目在范围 [0, 100] 内
    • 0≤Node.val≤1000 \leq Node.val \leq 1000≤Node.val≤100

二、解决思路和代码

1. 解决思路

  • 分析:借助一个头指针,以及四指针实现 翻转K个一组 的节点
    • step1: 借助一个头节点,方便后续修改指针指向操作

    • step2: 借助三个指针:pre, cur, last

      • cur: 指向 一组k个节点 的第一个节点

      • last: 指向 一组k个节点 的最后一个节点

      • pre: 指向 待交换一组k个节点 的前一个节点

      • 例如,当 k=3 时,先找到 pre, cur, last 所指向的节点:

    • step3: 翻转k个一组链表

      • 翻转前链表的最后一个节点为翻转后链表的第一个节点,修改: pre.next=last
      • 使用头插法实现K个一组翻转链表的操作:
        • 借助一个临时指针temp,指向待翻转链表的第一个节点


    • step4: 重复step2, step3,直到遍历所有节点

2. 代码

    from typing import *class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:if k==1: return head## step1:pre = ListNode(val=-1, next=head)head = prewhile pre.next:## step2:   cur = last = pre.nextcount = 1while count1:temp = curcur = cur.nextcount -= 1temp.next = last.nextlast.next = tempif k-count==1: pre = temp## if cur==last: pre = tempreturn head.next

相关内容

热门资讯

说方言郭德纲相声台词 说方言郭德纲相声台词  各位有认识我,有不认识。我是相声界非著名相声演员郭德纲。和小编一起来看看下文...
幼儿园毕业典礼主持稿开场白   幼儿园大班孩子即将挥别母校,那么在毕业典礼上应该如何说好主持词呢,以下是CN人才小编搜集并整理的...
小班元旦主持词 导语:幼儿园举办元旦晚会主持词怎么说?以下是小编整理的小班元旦主持词,欢迎阅读参考。小班元旦主持词a...
公司结训主持词 公司结训主持词  主持词要根据活动对象的不同去设置不同的主持词。时代不断在进步,各种场合中活跃现场气...
读书分享会的精彩主持词 读书分享会的精彩主持词  由主持人于节目进行过程中串联节目的串联词。如今的各种演出活动和集会中,主持...
幼儿园运动会入场主持词 有关幼儿园运动会入场主持词(精选12篇)  契合现场环境的主持词能给集会带来双倍的效果。随着社会一步...
毕业30年同学聚会致辞 毕业30年同学聚会致辞  毕业30年同学聚会致辞    2013年7月13日下午在吉安市林业局食堂三...
报告会主持词 【精选】报告会主持词4篇  主持词没有固定的格式,他的最大特点就是富有个性。在当今中国社会,主持成为...
过界男女的经典台词及微影评 过界男女的经典台词及微影评  过界男女经典台词  1、因为李先生的户口被冻结了,所以暂时不能为你办理...
中秋节商务贺卡祝词 中秋节商务贺卡祝词把酝酿已久的创意交给秋风,任其去演绎相思的旋律;让翘盼团聚的心跃上太空,在月宫桂树...
谢师宴酒席致辞 谢师宴酒席致辞(精选5篇)  无论是在学校还是在社会中,说到致辞,大家肯定都不陌生吧,致辞具有“礼仪...
快板书武松打虎台词 快板书武松打虎台词  快板书是起源于山东省汉族传统曲艺形式,具有一百多年的历史。它最早流行于山东、华...
学校元旦晚会开场白主持词 学校元旦晚会开场白主持词  根据活动对象的不同,需要设置不同的主持词。在一步步向前发展的社会中,越来...
长辈证婚人证婚词 长辈证婚人证婚词各位领导、各位来宾、各位朋友、女士先生们:大家好!华灯初放、嘉宾盈门,我怀着兴奋的心...
元宵节主持词 元宵节主持词15篇  主持词要根据活动对象的不同去设置不同的主持词。在如今这个时代,各种场合中活跃现...
宗亲联谊大会主持词 宗亲联谊大会主持词  主持词要注意活动对象,针对活动对象写相应的主持词。在人们越来越多的参与各种活动...
和谐之声新春联欢会主持台词稿 和谐之声新春联欢会主持台词稿  (联欢会开场前60分钟内,所有接待、服务、道具、灯光、音响、服装、化...
遗体告别主持词 2021遗体告别主持词范文(通用5篇)  主持词是各种演出活动和集会中主持人串联节目的串联词。在当下...
颁奖典礼主持词 关于颁奖典礼主持词(通用5篇)  主持词是各种演出活动和集会中主持人串联节目的串联词。在各种集会、活...
高中学生家长会主持词 高中学生家长会主持词汇编  许多家长把注意力集中在孩子的学习上,其实,作为家长更应该从侧面关心孩子的...