亲宝软件园·资讯

展开

Java输出链表结点

WYSCODER 人气:0

前言

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

总结

加载全部内容

相关教程
猜你喜欢
用户评论