首页 > 试题广场 >

输出单向链表中倒数第k个结点

[编程题]输出单向链表中倒数第k个结点

热度指数：235705 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

链表结点定义如下：

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

正常返回倒数第k个结点指针。

输入描述:

每一个测试用例会有多组。每一组的测试用例格式如下：第一行输入链表结点个数， 
第二行输入长度为的数组，表示链表的每一项， 
第三行输入的值，

输出描述:

每一组，输出倒数第k个结点的值

示例1

输入

3
1 2 3
1
8
1 2 3 4 5 6 7 8
4

输出

3
5

算法知识视频讲解

查看答案及解析

Java

牛客281381469号

自定义链表。
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            ListNode dummyhead = new ListNode(0);
            ListNode cur = dummyhead;
            for (int i = 0; i < n; i++){
                cur.next = new ListNode(in.nextInt());
                cur = cur.next;
            }
            int k = in.nextInt();
            ListNode slow = dummyhead;
            ListNode fast = dummyhead;
            for (int i = 0; i <= k; i++){
                fast = fast.next;
            }
            while(fast != null){
                slow = slow.next;
                fast = fast.next;
            }
            System.out.println(slow.next.val);
        }
    }
}
class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
        this.val = val;
    }
}

发表于 2025-07-20 18:49:54 回复(0)

Java

牛客853808348号

暴力输出

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while(in.hasNextInt()){
            int n = in.nextInt();
            int[] val = new int[n];
            for(int i=0;i<n;i++){
                val[i] = in.nextInt();
            }
            int k = in.nextInt();
            System.out.println(val[n-k]); 
        }
    }
}

发表于 2025-05-27 22:05:10 回复(0)

Java

Sen🍓🍀

import java.util.Scanner;

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 p = head;
            ListNode q = null;
            while (n-- > 0) {
                q = new ListNode(in.nextInt());
                p.next = q;
                p = q;
            }

            int k = in.nextInt();
            
            // 快慢指针 p慢 、q快k个
            p = head;
            q = head;
            while (k-- > 0) {  //q快k个
                q = q.next;
            }
            while (q != null) { //q到链表末时，p即倒k个
                p = p.next;
                q = q.next;
            }
            System.out.println(p.val);
        }
    }
}

// 链表结点
class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

复习了对象、快慢指针

发表于 2025-01-27 20:57:13 回复(0)

Java

认真的芝士在敲键盘

// 题解https://blog.nowcoder.net/n/8eedb64d7980415fa6ebe145c26be0b3?f=comment

// 设置两个指针，一个初始化指向第一个结点，第二个指向第k个结点。然后两个指针同步向后移动，当第二个指向尾结点时，第一个指针即指向了倒数第k个结点。

// 尾插法

// 注意类名必须为 Main, 不要有任何 package xxx 信息

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

while (sc.hasNext()) {

int n = Integer.parseInt(sc.next());

ListNode head = new ListNode(-1);

ListNode temp = head;

//生成链表

for (int i = 0; i < n; i++) {

ListNode node = new ListNode(sc.nextInt());

temp.next = node;

temp = temp.next;

}

int k = Integer.parseInt(sc.next());

//使用快慢指针

if (getKthFromEnd(head.next, k) != null) {

System.out.println(getKthFromEnd(head.next, k).val);

} else {

System.out.println(0);

}

//通过快慢指针搜索

public static ListNode getKthFromEnd(ListNode head, int k) {

if (head == null) return null;

ListNode fast = head, slow = head;

//快指针先走k步

for (int i = 0; i < k; i++) {

if (fast == null) return fast;

fast = fast.next;

}

while (fast != null) {

fast = fast.next;

slow = slow.next;

}

return slow;

}

class ListNode {

ListNode next;

int val;

ListNode(int val) {

this.val = val;

next = null;

}

发表于 2024-09-12 15:36:06 回复(0)

Java

牛客520067632号

import java.io.*;
//自定义链表节点类
class ListNode {
    int num;
    ListNode next;
    public ListNode() {}
    public ListNode(int l, ListNode n) {
        this.num = l;
        this.next = n;
    }

}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = null; 
        while ((str=bf.readLine()) != null) {
            //获取原始输入
            int len = Integer.parseInt(str);
            String[] num = bf.readLine().split(" ");
            int want = Integer.parseInt(bf.readLine());
            //创建链表头节点
            ListNode ls = new ListNode();
            //头插法将新节点插入链表头
            for (int i = 0; i < len; i++) {
                ListNode newC = new ListNode(Integer.parseInt(num[i]), ls);
                //更新头节点
                ls = newC;
            }
            //从头开始遍历链表直至满足条件
            while (ls != null && want != 1) {
                ls = ls.next;
                want--;
            }
            //输出对应节点
            System.out.println(ls.num);
        }

    }
}

发表于 2024-09-05 10:59:31 回复(0)

Java

爱吃香菜的小确幸在投简历

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int len = in.nextInt();
            in.nextLine();
            LinkedList<Object> list = new LinkedList<>();
            for (int i = 0; i < len; i++) {
                list.add(in.nextInt());
            }
            in.nextLine();
            int index = in.nextInt();
            System.out.println(list.get(len - index));
        }
    }
}

发表于 2024-07-06 21:21:32 回复(0)

Java

无梦0

要什么自行车

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) {
            out(in);
        }
    }

    private static void out(Scanner in) {
        int len = in.nextInt();
        List<Integer> li = new ArrayList();
        while (li.size() < len) { // 注意 while 处理多个 case
            li.add(in.nextInt());
        }
        int val = in.nextInt();
        if (val <= len) {
            System.out.println(li.get(len - val));
        }
    }
}

发表于 2024-04-08 13:00:41 回复(1)

Java

牛客214364484号

采用尾插法构建链表，正数第length-k+1个节点就是倒数第k个！

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int num = sc.nextInt();
            //构建带头节点的链表
            ListNode head = new ListNode();
            ListNode temp = head;//head不移动，利用中间变量来遍历
            for(int i = 0;i < num;i++){
                int val = sc.nextInt();
                ListNode node = new ListNode(val,temp.next);
                temp.next = node;//前一个节点的尾指向后一个节点
                temp = temp.next;//temp后移
            }
       
            int k = sc.nextInt();
            //查找倒数第K个节点
            if(getnum(head,k) != null){
                System.out.println(getnum(head,k).value);
            }
            else{
                System.out.println(0);
            }
        }
        sc.close();
    }

    public static ListNode getnum(ListNode head,int k){
        int length = 0;
        ListNode node = head.next;//从第一个节点开始计算长度
        //计算链表长度
        while(node != null){
            length++;
            node = node.next;
        }
        //查找倒数第K个节点
        if(length == 0 || k > length){//异常返回空指针
            return null;
        }

        node = head; //因为底下的for循环一进去i=0时候就已经node = node.next;把第一个节点的值给了node,所以此处不要写head.next
        for(int i = 0;i < length - k + 1;i++){//从头节点开始，正数length-k+1就是倒数第K个节点
            node = node.next;
        }

        return node;
    }
}


class ListNode{
    int value;
    ListNode next;

    public ListNode(){      //空参构造器

    }
    public ListNode(int value,ListNode next){     //全参构造器
        this.value = value;
        this.next = next;
    }
}

发表于 2024-01-12 19:04:00 回复(0)

Java

姚文帆

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int nodeNum = in.nextInt();
            //创建头指针和操作指针p，默认复制头指针给p，后面还会用到头指针所以需要两个指针
            ListNode headNode = new ListNode();
            ListNode p = headNode;
            for(int i = 0; i < nodeNum; i++){
                ListNode untilNode;
                untilNode = new ListNode(in.nextInt(),null);
                p.next = untilNode;
                p = untilNode;
            }
            int key = in.nextInt();
            ListNode newNode = null;
            for(int j = 0; j <= nodeNum-key; j++){
                newNode = headNode.next;
                headNode = newNode;
            }
            System.out.println(newNode.value);
        }
    }
}
class ListNode{
    int value;
    ListNode next;
    public ListNode(){}
    public ListNode(int value,ListNode next){
        this.value = value;
        this.next = next;
    }
}

这道题主要考察头插法

发表于 2023-12-15 12:11:51 回复(0)

Java

Kili_66

import java.util.Scanner;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        next = null;
    }
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
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(in.nextInt());
            ListNode p = head;
            for (int i = 1; i < n; i++) {
                ListNode node = new ListNode(in.nextInt());
                p.next = node;
                p = node;
            }
            int k = in.nextInt();
            p = head;
            ListNode q = head;
            while (k-- > 1) {
                p = p.next;
            }
            //如果p为空说明出现异常,否则p走到尾部，q就是倒数第k个节点
            while (p.next != null) {
                p = p.next;
                q = q.next;
            }
            System.out.println(q.val);
        }
    }
}

发表于 2023-11-25 00:48:37 回复(0)

Java

虎图图

假如我用数组求解，阁下又该如何应对呢？

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while(in.hasNextInt()){
          int n = in.nextInt();
          int[] num = new int[n];
          for(int i = 0;i < n;i ++){
              num[i] = in.nextInt();
          }
          int m = in.nextInt();
          if(m > n){
              return;
          }else{
              System.out.println(num[n - m]);
          }
        }
    }
}

发表于 2023-10-25 23:59:55 回复(1)

Java

GCID

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            ListNode head=getList(in);
            int k=in.nextInt();
            System.out.println(findReverseKth(head,k).m_nKey);
        }
    }

    private static ListNode findReverseKth(ListNode head,int k){
        ListNode curr=head;
        int n=0;
        while(curr!=null){
            curr=curr.m_pNext;
            n++;
        }
        int index=n-k;
        if(index>=0){
            curr=head;
            for(int i=0;i<index;i++){
                curr=curr.m_pNext;
            }
            return curr;
        }

        return null;
    }

    private static ListNode getList(Scanner in){
        int n=in.nextInt();
        ListNode headPrev=new ListNode();
        ListNode curr=headPrev;
        for(int i=0;i<n;i++){
            curr.m_pNext=new ListNode(in.nextInt());
            curr=curr.m_pNext;
        }
        return headPrev.m_pNext;
    }


    static class ListNode{
        int m_nKey;
        ListNode m_pNext;
        public ListNode(){
            m_pNext=null;
        }
        public ListNode(int key){
            m_nKey=key;
            m_pNext=null;
        } 
    }
}

发表于 2023-09-10 20:37:10 回复(0)

Java

crestalpin0504

while(in.hasNextInt()){

int n=in.nextInt();

List<Integer> ls= new LinkedList<>();

for(int i=0;i<n;i++){

ls.add(in.nextInt());

}

int index=in.nextInt();

System.out.println(ls.get(ls.size()-index));

}

发表于 2023-06-08 10:43:38 回复(1)

Java

梁山教父

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n=in.nextInt();
            //用list来构造链表，效果相同，不用其长度
            ArrayList<Integer> list=new ArrayList<>();
            for(int i=0;i<n;i++){
                list.add(in.nextInt());
            }
            int k=in.nextInt();
            int num=0;
            int left=0;
            int right=0;
            //忘记链表长度
            while(true){
                //相当于right节点==null的效果
                if(right==list.size()-1){
                    //当right节点null时，将left节点位置的值输出
                    num=list.get(left);
                    break;
                }
                //维护位置
                if(right-left!=k-1){
                    right++;
                }else{
                    right++;
                    left++;
                }
            }
            System.out.println(num);
        }
    }
}

发表于 2023-05-31 10:09:07 回复(0)

Java

练习时长两年半的太平湖水怪很理智

import java.io.*;

//创建节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        next = null;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = br.readLine()) != null) {
            int n = Integer.parseInt(str);
            String[] strArr = br.readLine().trim().split(" ");
            int k = Integer.parseInt(br.readLine());
            //创建第首节点，不带头节点（因为该首节点数据区是有值，带头节点的链表含有一个数据区为空的节点用于指向首节点）
            ListNode head = new ListNode(Integer.parseInt(strArr[0]));
            //创建临时节点，指向首节点
            ListNode temp = head;
            //创建链表
            for (int i = 1; i < n; i++) {
                ListNode Node = new ListNode(Integer.parseInt(strArr[i]));
                temp.next = Node;
                temp = temp.next;
            }
            //直接输出第k个几点的值
            System.out.println(getNodeFromEnd(head, k).val);
        }

    }
    //题目要求构建后要忘记链表长度，即不让用main方法中获得的n，所以需要重新获得链表的长度
    private static ListNode getNodeFromEnd(ListNode head, int k) {
        //如果head.next == null，则链表只有一个节点，即只有head，题目已经规定链表长度为1到1000，所以不可能为空
        if (head.next == null) return head;
        int num = 0;
        ListNode temp = head;
        //temp != null说明已经统计完所有节点
        while (temp != null) {
            num++;
            temp = temp.next;
        }
        temp = head;
        //获取倒数第k个节点
        for (int i = 1; i <= num - k; i++) {
            temp = temp.next;
        }
        return temp;
    }
}

发表于 2023-05-12 20:34:11 回复(0)

Java

痴心的变色龙要暴富

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int a = in.nextInt();

LinkedNode list = new LinkedNode();

//循环插入元素

for (int i = 0; i < a; i++) {

int val = in.nextInt();

list.insert(val);

}

int num = in.nextInt();

//获取倒数第k个元素

System.out.println(list.search(num));

}

class LinkedNode {

Node head;

class Node {

int val;

Node next;

Node(int val) {

this.val = val;

}

//正序构建链表(尾插法)

public void insert(int val) {

Node newNode = new Node(val);

if (head == null) {

head = newNode;

} else {

Node cur = head;

while (cur.next != null) {

cur = cur.next;

}

cur.next = newNode;

}

//逆序遍历时无需通过链表长度

public int search(int num) {

Node right = head;

Node left = head;

int i = 0;

while (right.next != null) {

i++;

if (i >= num) {

left = left.next;

}

right = right.next;

}

return left.val;

}

发表于 2023-04-09 20:31:33 回复(0)

Java

不放弃的放鸽子能手很帅气

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

while (scanner.hasNext()) {

int length = scanner.nextInt();

int headVal = scanner.nextInt();

ListNode header = new ListNode(headVal, null);

ListNode temp = header;

for (int i = 0; i < length - 1; i++) {

int value = scanner.nextInt();

ListNode node = new ListNode(value,null );

temp.next = node;

temp = node;

}

int k = scanner.nextInt();

//ListNode 头结点为header

ListNode cur = header;

for (int i = 0; i < k - 1; i++) {

if (cur.next == null)

return;

cur = cur.next;

}

ListNode result = header;

while (cur.next != null) {

cur = cur.next;

result = result.next;

}

System.out.println(result.val);

}

static class ListNode {

int val;

ListNode next = null;

public ListNode(int val, ListNode next) {

this.val = val;

this.next = next;

}

发表于 2023-03-11 13:46:00 回复(0)

Java

牛客268032525号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int size = in.nextInt();
            ListNode dummy = new ListNode(-1, null);
            ListNode curr = dummy;
            for (int i = 0; i < size; i++) {
                int x1 = in.nextInt();
                curr.next = new ListNode(x1, null);
                curr = curr.next;
            }
            int k = in.nextInt();
            ListNode p = dummy, q = dummy;
            for (int i = 0; i < k; i++) {
                p = p.next;
            }
            while (p != null) {
                p = p.next;
                q = q.next;
            }
            System.out.println(q.val);
        }
        in.close();
    }
}
class ListNode {
    int val;
    ListNode next;

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

发表于 2023-03-02 13:49:49 回复(0)

Java

无敌壮壮

import java.io.*;//使用LinkedList集合实现数据以链表形式添加存储和查询
import java.util.LinkedList;
import java.util.List;
/**
用到方法：Integer.parseInt(str);s.readLine().split(" ");List<Object> list = new LinkedList<>();list.add(arr[i]);list.get(n - k)
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        int n;
        String str;
        while((str=s.readLine())!=null){//多组输入
            n = Integer.parseInt(str);
        String[] arr = s.readLine().split(" ");
        int k = Integer.parseInt(s.readLine());
        List<Object> list = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }
        System.out.println(list.get(n - k));
        }
    }
}

发表于 2023-01-21 14:59:04 回复(0)

Java

大胆的花生米在吵架

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int len = in.nextInt();
            int[] data = new int[len];
            for (int i = 0; i < len; i++) {
                data[i] = in.nextInt();
            }
            int pos = in.nextInt();

            int lastPos = len - pos;
            System.out.println(data[lastPos]);
        }
    }
}

发表于 2022-12-08 18:01:04 回复(0)