华为机试练习题：HJ51 输出单向链表中倒数第k个结点

1、Java代码（直接运行版）

package listnodes;
 
import java.util.Scanner;
 
//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
 
public class LinkedListTest {
    public static void main(String[] args) {
 
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
        //正序构建链表
        ListNode head = new ListNode(-1);
        ListNode temp = head;
        for (int i = 0; i < nums.length; i++) {
            ListNode node = new ListNode(nums[i]);
            temp.next = node;
            temp = temp.next;
        }
        head = head.next;//去掉虚拟头节点就是构建好的完整链表
 
        //构建链表后，忘记链表长度，重新遍历链表，找到倒数第k个节点
        int k = 4;
        ListNode pre = head;
        ListNode rear = head;
        int count = 1;
        while(rear.next != null && count < k){
            count++;
            rear = rear.next;
        }
        while(rear.next != null){
            rear = rear.next;
            pre = pre.next;
        }
        System.out.println(pre.val);//5
    }
}

2、Java代码（牛客提交版）

import java.util.Scanner;
 
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
 
public class Main {
        public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int n = in.nextInt();
            //正序构建链表
            ListNode head = new ListNode(-1);
            ListNode temp = head;
            for (int i = 0; i < n; i++) {
                ListNode node = new ListNode(in.nextInt());
                temp.next = node;
                temp = temp.next;
            }
            head = head.next;//去掉虚拟头节点就是构建好的完整链表
 
            //构建链表后，忘记链表长度，重新遍历链表，找到倒数第k个节点
            int k = in.nextInt();
            ListNode pre = head;
            ListNode rear = head;
            int count = 1;
            while (rear.next != null && count < k) {
                count++;
                rear = rear.next;
            }
            while (rear.next != null) {
                rear = rear.next;
                pre = pre.next;
            }
            System.out.println(pre.val);
        }
    }
}

3、完整题目

输出单向链表中倒数第k个结点_牛客题霸_牛客网

描述

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

链表结点定义如下：

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

正常返回倒数第k个结点指针，异常返回空指针.

要求：

(1)正序构建链表;

(2)构建后要忘记链表长度。

数据范围：链表长度满足 1≤n≤1000  ，  k≤n  ，链表中数据满足  0≤val≤10000 

本题有多组样例输入。

输入描述：

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

输出描述：

输出一个整数

示例1

输入：

8
1 2 3 4 5 6 7 8
4

输出：

5