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


猜你喜欢
- 背景今天学习Springboot,但是用的apache-maven 3.0 ,导入springboot1.5.19 ,Maven项目老是爆红
- 本文实例讲述了Android编程简单实现雷达扫描效果。分享给大家供大家参考,具体如下:在eoe看到有一篇关于雷达扫描的文章,然后看了下,很简
- flutter中的布局flutter布局机制的核心是组件。在flutter中,几乎所有的东西都是组件,布局模型也不例外。图片,Icon, 文
- 已经下过好几次了,现在还是忘了。就把过程直接放上面了。下次再换电脑就直接可以看。。。0.下载之前需要把JDK安装和配置好,点这里:https
- 简介本文介绍Idea如何根据maven依赖名查找它是哪个pom.xml引入的。有时候会有这样的问题:我们知道项目里用了某个依赖,想知道它是项
- 两个接口都是继承自Collection.List (inteface) 次序是List 的最重要特点,它确保维护元素特定的顺序. --Arr
- 本文实例讲述了Android实现的仿淘宝购物车。分享给大家供大家参考,具体如下:夏的热情渐渐退去,秋如期而至,丰收的季节,小编继续着实习之路
- 创蓝253: https://www.253.com/#region 获取手机验证码(创蓝253) /// <summar
- 近期用到了一位师兄写的C++程序,总体功能良好。使用不同的数据测试,发现了一个明显的缺点:大数据量下,预处理过程耗时很长。中科院的某计算集群
- SpringBoot的主要目的是简化配置文件,通过少量配置即可运行Java程序,其强大的自动配置功能帮助开发者轻松实现配置装配,通过引入Sp
- 首先来个效果图 布局文件代码在布局文件中,CoordinatorLayout作为布局文件根节点,AppBarLayo
- 做一个五子棋练练手,没什么特别的,再复习一下自定义View的知识,onMeasure,MeasureSpec , onDraw以及OnTou
- 背景在写一个东西滑动删除列表的时候,出现了一个问题。我的需求是,左滑然后出现delete,然后点击delete,让该滑块消失。我在点列表的第
- C#备忘录设计模式大家好,老胡又和大家见面了。首先承认今天的博客有点标题党了,人生是没有存档,也没有后悔药的。有存档和后悔药的,那是游戏,不
- 本文作者:Spring_ZYL文章来源:https://blog.csdn.net/gozhuyinglong版权声明:本文版权归作者所有,
- 本文实例为大家分享了C#泛型类创建与使用的具体代码,供大家参考,具体内容如下using System;using System.Collec
- Android 使用log4j前言: 如果要直接在android工程中使用log4j,是有点问题的,会报如下的错: 1
- 最近要做动态数据的提交处理,即需要分析提交数据字段定义信息后才能明确对应的具体字段类型,进而做数据类型转换和字段有效性校验,然后做业务处理后
- mybatis多层级collection嵌套json结构第一步查询第一层查询,将第一层的id传递到第二层当条件查询
- 绝对路径:不可改变的路径本地绝对路径:增加盘符的路径(e:/test/test.html)网络绝对路径:增加协议,IP地址,端口号的路径(h