首页 > 编程语言 ># 92 -「java 」 100-执行速度 - 三步『截取子链表- 递归反转- 拼接』 解题的实现思路

# 92 -「java 」 100-执行速度 - 三步『截取子链表- 递归反转- 拼接』 解题的实现思路

时间:2023-03-14 20:34:05浏览次数:53  
标签:head ListNode 反转 next 链表 java 92 节点

Tags

  • 中等

  • 递归

  • 链表

  • java

 

题目链接:

92. 反转链表 II

 

解题思路[截取子链表 + 反转 + 拼接]:

以1->2->3->4->5, m = 2, n=4 为例:

  • 【截取】定位到需要反转的头结点2, start=2; 前驱节点为1, pre=1; 需要反转的末位节点为4, last=4; 反转子链表的后驱节点为5, next=5;

  • 【反转子链表】需要反转2->3->4的子链表, 通过递归实现

注意: 此步骤反转的是子链表, 所以不能像 206.反转链表 一样, 使用head==null || head.next== null作为递归终止条件, 需要使用子链表长度count来作为终止条件

  • 【拼接】重新把 前驱节点(1)-> 反转后的子链表(4->3->2) -> 后驱节点(5) 拼接起来, 返回head即可

 

实现代码:

 class Solution {
     public ListNode reverseBetween(ListNode head, int left, int right) {
         if(head.next == null){
             return head;
        }
         //1. 拆分
         ListNode pre = new ListNode();    //需要反转子链表的前驱节点
         pre.next = head;    //自定义节点, 用于处理left==1的情况
 ​
         ListNode start = head;  //需要反转的头节点
         ListNode last = null;   //需要反转的尾节点
         ListNode next = null;   //需要反转子链表的后驱节点
 ​
         ListNode curr = head;   //遍历的当前位
         for(int i = 0; i<right; i++){   //遍历链表, 对各个节点变量赋值
             if(i == left-2){    //
                 pre = curr;
                 start = curr.next;
            }
             if(i == right-1){
                 last = curr;
                 next = curr.next;
            }
             curr = curr.next;
        }
         //2. 反转(回溯)
         this.backdate(start, (right-left));
         //3. 拼接
         pre.next = last;
         start.next = next;
 ​
         return left==1 ? pre.next : head;   //判断是否从第一位开始反转
    }
 ​
     //递归反转子链表
     public ListNode backdate(ListNode head, int count){
         if(count == 0){
             return head;
        }
         ListNode cur = backdate(head.next, count-1);
         head.next = null;
         cur.next = head;
         return head;
    }
 }

 

提交记录[20210629]:

标签:head,ListNode,反转,next,链表,java,92,节点
From: https://www.cnblogs.com/zhiyuanzag/p/17216243.html

相关文章

  • Java Mybatis 笔记
    MyBatis1、简介1.1什么是MybatisMyBatis是一款优秀的持久层框架;它支持自定义SQL、存储过程以及高级映射。MyBatis免除了几乎所有的JDBC代码以及设置参数和获......
  • CFR 反编译 Java 枚举
    CFR到这里下载。运行如下命令使用当前文件夹下的cfr-0.152.jar反编译当前文件夹下的T.class。java-jarcfr-0.152.jarT.class--sugarenumsfalse其中--sugarenum......
  • Java的HashMap
    基于hash值的K-V结构数据容器。重要计算方法计算key的hash值(key==null)?0:(h=key.hashCode())^(h>>>16)利用hash计算tab中的位置p=tab[i=(n-1)&......
  • java变量和常量
    一标识符我们所认识的标识符如:类名HelloWorld标识符的命名规则标识符可以由字母,数字,下划线和和美元符$组成,不能以数字开头标识符严格区分大小写标识符......
  • java实体类之间的转换
    字段相同BeanUtils.copyProperties(item,dto);字段不同通过mapstruct,定义不同的字段名字https://blog.csdn.net/weixin_55806809/article/details/125347999......
  • 平安金服java岗
    电话一面面试官很和蔼,会适度闲聊,奈何本人全程很紧绷,自我介绍之后被安抚别太紧张 ̄□ ̄||1.自我介绍2.最近的一次项目概况,技术难点,怎么攻克的(我自爆代码是网上找的,真无语,一紧张......
  • Java容器之Hashtable源码分析
    一、概述Hashtable是一个比较古老的Map实现类,从它的名称就可以看得出来,因为没有遵循Java的语言规范。它和HashMap很像,同属于散列表,有以下特性:线程安全,这也估计算是唯一......
  • nacos报错 Caused by: com.alibaba.nacos.api.exception.NacosException: java.io.IOE
    麻麻劈,根据这个报错一顿ulimit -n 修改打开文件数,鸡儿报错一直在。 最终修改 vi/etc/sysctl.conf增加三项:fs.inotify.max_queued_events=32768fs.inotify.ma......
  • vscode 中如何运行一个 java 的 hello world
    经常遇到遇到需要运行一些片断性的的代码,比如调试一个函数是否符合预期,在小项目中,又不想写单元测试,就需要一个轻量化的工具,vscode可以轻松胜任。以下内容来自ChatGPT,经本......
  • JavaSE-day02(面向对象:内部类,枚举,泛型)
    一、内部类内部类是类中的五大成分之一(成员变量、方法、构造器、内部类、代码块),如果一个类定义在另一个类的内部,这个类就是内部类。当一个类的内部,包含一个完整的事物,且......