描述

输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。

链表结点定义如下：

struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
正常返回倒数第k个结点指针，异常返回空指针

本题有多组样例输入。

输入描述：
输入说明
1 输入链表结点个数
2 输入链表的值
3 输入k的值

输出描述：
输出一个整数

示例：

输入：
8
1 2 3 4 5 6 7 8
4

输出：
5

解法

此题考查如何链表数据结构的操作。Java API提供了LinkedList结构，但显然直接用这个结构未免显得无法彰显技术功底。因此，需要自己实现一个链表数据。

单向链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成单向链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。

有关链表数据结构的实现，可以参考 《数据结构和算法基础（Java 语言实现）》这本书，里面有详细的介绍。本题只是实现了链表的最基础的功能，直接看代码：

 /*
  * Copyright (c) waylau.com, 2022. All rights reserved.
 */

package com.waylau.nowcoder.exam.oj.huawei;

import java.util.Scanner;


/**
 * HJ51 输出单向链表中倒数第k个结点.
 * 描述：输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。
 * 正常返回倒数第k个结点指针，异常返回空指针
 * 输入描述：
 * 输入说明
 * 1 输入链表结点个数
 * 2 输入链表的值
 * 3 输入k的值
 * 输出描述：
 * 输出一个整数
 * 示例：
 * 输入：
 * 8
 * 1 2 3 4 5 6 7 8
 * 4
 * 输出：
 * 5
 *
 * @author <a href="">Way Lau</a>
 * @since 2022-08-26
 */
public class HJ051OutputTheKthToLastNodeInTheUnidirectionalLinkedList {
    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);

        while(in.hasNext()) {
            int n =  in.nextInt();

            MyLinkedList list = new MyLinkedList();
            for (int i = 0; i< n;i++) {
                list.add(in.nextInt());
            }

            int k = in.nextInt();

            // 输出
            System.out.println(list.get(n - k));
        }

        // 关闭
        in.close();
    }
}

class Node {
    public int data;

    public Node next;

    public Node(int data) {
        this.data = data;
    }
}

class MyLinkedList {
    // 实际链表里面的元素个数
    private int size = 0;

    // 头节点
    private Node first;

    // 尾节点
    private Node last;

    public MyLinkedList() {
    }


    public boolean add(int e) {
        final Node l = last;

        // 构造一个新节点
        final Node  newNode = new Node (e);
        last = newNode;

        // 判断尾节点，尾节点为null，则证明链表是空的。
        // 如果链表是空的，新增加的节点就作为头结点；
        // 如果链表是不空，则原尾节点的next指向新增加的节点
        if (l == null) {
            first = newNode;
            last = newNode;
        } else {
            l.next = newNode;
        }

        size++; // size累加1位

        return true;
    }

    public int get(int index) {
        // 判断是否越界
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException(
                    "index " + index + " out of bounds");
        }

        Node x = first;

        // 遍历链表
        for (int i = 0; i < index; i++) {
            x = x.next;
        }

        return x.data;
    }

}

参考引用