如何利用Java輸出鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
前言
鏈表是一種數(shù)據(jù)結(jié)構(gòu)，和數(shù)組同級(jí)。比如，Java中我們使用的ArrayList，其實(shí)現(xiàn)原理是數(shù)組。而LinkedList的實(shí)現(xiàn)原理就是鏈表了。鏈表在進(jìn)行循環(huán)遍歷時(shí)效率不高，但是插入和刪除時(shí)優(yōu)勢明顯
本文主要介紹的是輸出鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)，下面來一起看看詳細(xì)的介紹吧
問題描述
給你一個(gè)單鏈表，輸出倒數(shù)第k個(gè)結(jié)點(diǎn)，如下圖鏈表中，輸出倒數(shù)第k個(gè)結(jié)點(diǎn)，比如 k = 2，輸出5這個(gè)結(jié)點(diǎn)。
方法一
方法描述
輸出倒數(shù)第k個(gè)結(jié)點(diǎn)就是輸出整數(shù)第len - k + 1個(gè)結(jié)點(diǎn)，len為鏈表的長度。
動(dòng)畫演示
代碼如下
/**
* 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 {
//計(jì)算鏈表的長度
private int size() {
int count = 0;
for(Node p = head;p != null;p = p.next) {
count++;
}
return count;
}
//返回倒數(shù)第k個(gè)結(jié)點(diǎn)
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）定義一個(gè)q變量指向鏈表的第一個(gè)結(jié)點(diǎn)，是q變量往后移動(dòng)k個(gè)結(jié)點(diǎn)。
2）定義一個(gè)p變量指向鏈表的第一個(gè)結(jié)點(diǎn)。
3）p變量和q變量同時(shí)循環(huán)往后移動(dòng)一個(gè)結(jié)點(diǎn)，直到q為null。
動(dòng)畫演示
代碼如下
/**
* 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 {
//計(jì)算鏈表的長度
private int size() {
int count = 0;
for(Node p = head;p != null;p = p.next) {
count++;
}
return count;
}
//返回倒數(shù)第k個(gè)結(jié)點(diǎn)
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往后移動(dòng)k個(gè)結(jié)點(diǎn)
while(k-- > 0) {
q = q.next;
}
Node p = head;
while( q != null) {
q = q.next;
p = p.next;
}
return p;
}
總結(jié)
到此這篇關(guān)于如何利用Java輸出鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)的文章就介紹到這了,更多相關(guān)Java輸出鏈表結(jié)點(diǎn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java實(shí)現(xiàn)分頁的前臺(tái)頁面和后臺(tái)代碼
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)分頁的前臺(tái)頁面和后臺(tái)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-03-03
Eclipse+Webservice簡單開發(fā)實(shí)例
這篇文章主要介紹了Eclipse+Webservice簡單開發(fā)實(shí)例的相關(guān)資料,需要的朋友可以參考下2016-02-02
SpringBoot在項(xiàng)目停止(服務(wù)停止/關(guān)閉退出)之后執(zhí)行的方法
這篇文章主要給大家介紹了SpringBoot在項(xiàng)目停止(服務(wù)停止/關(guān)閉退出)之后執(zhí)行的兩種方法,實(shí)現(xiàn)DisposableBean接口和使用@PreDestroy注解,文中有詳細(xì)的代碼講解,具有一定的參考價(jià)值,需要的朋友可以參考下2023-12-12
JSP服務(wù)器端和前端出現(xiàn)亂碼問題解決方案
深入了解Java中String、Char和Int之間的相互轉(zhuǎn)換
Java實(shí)現(xiàn)在線預(yù)覽的示例代碼(openOffice實(shí)現(xiàn))
tio-boot?jfinal-plugins框架整合redis示例詳解
