快捷導(dǎo)航

如何利用Java輸出鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

更新時(shí)間：2021年12月10日 10:19:47 作者：WYSCODER

這篇文章主要給大家介紹了關(guān)于如何利用Java輸出鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用java具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

前言

鏈表是一種數(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;	
}