如何利用Java输出链表中倒数第k个结点

前言

链表是一种数据结构，和数组同级。比如，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