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

如何利用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 = http://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;

DARHkqALfor(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;

}

总结

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。