如何利用Java输出链表中倒数第k个结点
作者:WYSCODER 发布时间:2022-11-29 10:13:28
标签:java,链表,结点
前言
链表是一种数据结构,和数组同级。比如,Java中我们使用的ArrayList,其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高,但是插入和删除时优势明显
本文主要介绍的是输出链表中倒数第k个结点,下面来一起看看详细的介绍吧
问题描述
给你一个单链表,输出倒数第k个结点,如下图链表中,输出倒数第k个结点,比如 k = 2,输出5这个结点。
方法一
方法描述
输出倒数第k个结点就是输出整数第len - k + 1个结点,len为链表的长度。
动画演示
代码如下
/**
* Definition for singly-linked list.
* public class Node {
* int val;
* Node next;
* Node() {}
* Node(int val) { this.val = val; }
* Node(int val, Node next) { this.val = val; this.next = next; }
* }
*/
class Solution {
//计算链表的长度
private int size() {
int count = 0;
for(Node p = head;p != null;p = p.next) {
count++;
}
return count;
}
//返回倒数第k个结点
public Node outputLastIndexNode(int k) {
//链表为空
if (head == null) {
return null;
}
//链表长度
int len = size();
//检测k值
if(k > len || k < 0) {
System.out.println("k值有误!!!");
}
Node p = head;
for(int i = 0; i < len - k; i++) {
p = p.next;
}
return p;
}
方法二
方法描述
1)定义一个q变量指向链表的第一个结点,是q变量往后移动k个结点。
2)定义一个p变量指向链表的第一个结点。
3)p变量和q变量同时循环往后移动一个结点,直到q为null。
动画演示
代码如下
/**
* Definition for singly-linked list.
* public class Node {
* int val;
* Node next;
* Node() {}
* Node(int val) { this.val = val; }
* Node(int val, Node next) { this.val = val; this.next = next; }
* }
*/
class Solution {
//计算链表的长度
private int size() {
int count = 0;
for(Node p = head;p != null;p = p.next) {
count++;
}
return count;
}
//返回倒数第k个结点
public Node outputLastIndexNode(int k) {
//链表为空
if (head == null) {
return null;
}
//链表长度
int len = size();
//检测k值
if(k > len || k < 0) {
System.out.println("k值有误!!!");
}
Node q = head;
//使q往后移动k个结点
while(k-- > 0) {
q = q.next;
}
Node p = head;
while( q != null) {
q = q.next;
p = p.next;
}
return p;
}
来源:https://blog.csdn.net/sheng0113/article/details/121799644
0
投稿
猜你喜欢
- 目录ShutdownHook介绍ShutdownHook原理ShutdownHook的数据结构与执行顺序ShutdownHook触发点Shu
- timer的schedule和scheduleAtFixedRate方法一般情况下是没什么区别的,只在某个情况出现时会有区别--当前任务没有
- 本文实例讲述了Java链表(Linked List)基本原理与实现方法。分享给大家供大家参考,具体如下:在分析链表之前,我们先来对之前的动态
- 引言一个复杂的分布式系统,用户发起一个请求,这个请求可能调用几十到几百个服务,经过很多业务层,而每个业务又是多个机器集群,一个请求具体被随机
- 1、引入依赖<dependency> <groupId>org.apache.pdfbox</gr
- 随着C语言的学习慢慢结束,博主也要开始学习一门新语言了,那就是java。所以博主将会开启一个新的关于java的专栏,所以想要慢慢和我一起学习
- 前言由于现在网络层已经升级到RxJava2.x相关的了,所以需要做些调整。虽然RxJava1.x和RxJava2.x同属RxJava系列,但
- Google 发布的Material Design支持库,对我们的APP设计有很大的影响,如果重新设计APP,支持库应该直接用V4提升到V7
- 在 MyEclipse 的可视化 Swing 中,有 JTable 控件。JTable 用来显示和编辑常规二维单元表。那么,如何将 数据库S
- Java Memory Model简称JMM, 是一系列的Java虚拟机平台对开发者提供的多线程环境下的内存可见性、是否可以重排序等问题的无
- 使用通配符增强泛型1.题目泛型是JAVA重要的特性,使用泛型编程,可以使代码复用率提高。实现:在泛型方法中使用通配符2.解题思路创建一个类:
- 这篇文章主要介绍了Spring JDK * 实现过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要
- 在讲述这个模式之前,我们先看一个案例:游戏回档游戏的某个场景,一游戏角色有生命力、攻击力、防御力等数据,在打Boss前和后会不一样,我们允许
- 大家好,在这篇文章中,我们将学习如何添加动画,同时从一个页面到其他在 Flutter。我们将覆盖不同类型的动画和实现基本动画 Flutter
- 目录1、如果一个方法或变量是"private"访问级别,那么它的访问范围是:2、代码将打印?3、下面关于hibernat
- 简介方案对比本处列举表示类型或状态的常用方法的对比。法1:使用数字表示(不推荐)//1:支付宝支付;2:微信支付;3:银行卡支付privat
- 本文实例讲述了C#实现对Json字符串处理方法,分享给大家供大家参考。具体分析如下:一般对于web应用开发人员来说对Json字符串都会很熟悉
- 安装hbase首先下载hbase的最新稳定版本 http://www.apache.org/dyn/closer.cgi/hbas
- 本文实例为大家分享了java实现文件下载的具体代码,供大家参考,具体内容如下public HttpServletResponse downl
- 前言在原生的 Android 或 iOS 中,都提供了基本的键值对存储方式,Android 是 SharedPreferences,iOS