Java输出链表倒数第k个节点
作者:lilivian 发布时间:2023-03-22 01:22:34
标签:java,链表,节点
问题描述
输入一个链表,输出该链表中倒数第k个结点。(尾结点是倒数第一个)
结点定义如下:
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
思路1:
先遍历链表,计算其长度length;
然后计算出倒数第k个结点就是正数第length - k + 1.
最后再遍历链表,找到所求结点
时间复杂度O(2n),需要遍历两次链表
代码如下:
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0){
return null;
}
//直接遍历
ListNode p = head;
int length = 1;
while(p.next != null){
length++;
p = p.next;
}
int index = length - k + 1;
if(index <= 0){
return null;
}
p = head;
int num = 1;
while(p.next != null && num < index){
num++;
p = p.next;
}
if(num < index){
return null;
}else{
return p;
}
}
思路2:
期待只遍历链表一次就能得到。
设置两个指针,一个初始化指向第一个结点,第二个指向第k个结点。然后两个指针同步向后移动,当第二个指向尾结点时,第一个指针即指向了倒数第k个结点
代码:
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0){
return null;
}
//直接遍历
ListNode p = head;
ListNode q = head;
for(int i = 0; i < k-1; i++){
if(q == null){
return null;
}
q = q.next;
}
if(q == null){
return null;
}
while(q.next != null){
p = p.next;
q = q.next;
}
return p;
}
思路3:
将链表反转,那么原问题就变为求正数第k个结点。
然而这改变了原本的链表,且并不会比思路2更高效
链表反转:参考《Java语言实现反转链表代码示例》
来源:http://blog.csdn.net/lilianforever/article/details/51839755
0
投稿
猜你喜欢
- Springboot 内置tomcat禁止不安全HTTP方法1、在tomcat的web.xml中可以配置如下内容让tomcat禁止不安全的H
- import java.util.regex.Matcher;import java.util.regex.Pattern; /*
- FTP 是File Transfer Protocol(文件传输协议)的英文简称,而中文简称为“文传协议”。用于Internet上的控制文件
- 1. 多行编辑先来体验一下从xml文件拷贝字段新建实体对象一般我们为了新建多表连接后映射的 ResultMap ,耗费不少时间,那么我们就来
- 背景客户使用我们系统的时候,查询不带任何查询条件,查询就返回全部数据,500多万条数据啊,然后直接导出,数据量庞大,接口超时,这可苦了我们这
- 本文实例讲述了C#计算矩阵的逆矩阵方法。分享给大家供大家参考。具体如下:1.代码思路1)对矩阵进行合法性检查:矩阵必须为方阵2)计算矩阵行列
- 前言本章是关于Java数组的最全汇总,本篇为汇总中篇,主要讲了二维数组和不规则的数组的相关内容。数组是最常见的一种数据结构,它是相同类型的用
- Bitmap (android.graphics.Bitmap)Bitmap是Android系统中的图像处理的最重要类之一。用它可以获取图像
- JMMJMM是指Java内存模型,不是Java内存布局,不是所谓的栈、堆、方法区。每个Java线程都有自己的工作内存。操作数据,首先从主内存
- 第一种方式:使用@Param注解方式此种方式用法是我们在接口中写方法的参数时,在每个参数的前面加上一个@Param注解即可。该注解有一个va
- 封装类用于阻止系统休眠的C#类。以下是代码注释的解释:DllImport("kernel32.dll"):定义了一个AP
- 在项目中有一个需求是需要在局域网内跨PC远程调用一个程序,并且要求有界面显示,调查了一些资料,能实现远程调用的.Net技术大概有PsExec
- 一、组件型注解:1、@Component 在类定义之前添加@Component注解,他会被spring容器识别,并转为bean。2、@Rep
- 你好,我是小黄,一名独角兽企业的Java开发工程师。感谢茫茫人海中我们能够相遇,俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心
- 在项目开发中,经常碰到map转实体对象或者对象转map的场景,工作中,很多时候我们可能比较喜欢使用第三方jar包的API对他们进行转化,而且
- 声明式事务回顾事务事务在项目开发过程非常重要,涉及到数据的一致性的问题,不容马虎!事务管理是企业级应用程序开发中必备技术,用来确保数据的完整
- FFmpeg是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化
- Comparable 比较器,内置定义的比较方法,实现比较 较简单Comparator 策略模式,需要定义不同的策略和比较的对象,实现比较
- 基于JavaFX开发桌面程序注:我也是JAVA FX的初学者之一,自己在学习的时候踩了许多的坑,中文英文的资料查了不少,但是觉得FX技术和其
- 1:同步调用:一种阻塞式调用,调用方要等待对方执行完毕才返回,它是一种单向调用 2:回调:一种双向调用模式,也就是说,被调用方在接口被调用时