如何利用Java输出链表中倒数第k个结点
短信预约 -IT技能 免费直播动态提醒
前言
链表是一种数据结构，和数组同级。比如，Java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显
本文主要介绍的是输出链表中倒数第k个结点，下面来一起看看详细的介绍吧
问题描述
给你一个单链表，输出倒数第k个结点，如下图链表中，输出倒数第k个结点，比如 k = 2，输出5这个结点。
方法一
方法描述
输出倒数第k个结点就是输出整数第len - k + 1个结点，len为链表的长度。
动画演示
代码如下
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。
动画演示
代码如下
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;
}
总结
到此这篇关于如何利用Java输出链表中倒数第k个结点的文章就介绍到这了,更多相关Java输出链表结点内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
