输出单链表倒数第K个节点-Java

╰+攻爆jí腚メ 2022-03-17 21:25 164阅读 0赞

## 题目描述： ##

输出一个单向链表，找出倒数第k个结点的值  
输入描述：  
1.输入链表结点的个数  
2.输入链表的值  
3.输入k的值  
示例1：  
输入：  
8  
1 2 3 4 5 6 7 8  
7

输出：  
2

## 代码： ##

方法一：用LinkedList实现

import java.util.LinkedList;
    import java.util.Scanner;
    
    public class Test {
        static class Node {
            int data;
            Node next;
            public Node(int data) {
                this.data = data;
            }
        }
    
        public static Integer find(Node head, int k) {
            if (head == null) {
                return null;
            }
            Node fast = head;
            Node slow = head;
            while (--k>0){
                fast = fast.next;
            }
            while (fast.next!=null){
                fast=fast.next;
                slow = slow.next;
            }
            return slow.data;
        }
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            LinkedList<Integer> s = new LinkedList<>();
            Node last = null;
            Node head = null;
            for (int i = 0; i < n; i++) {
                if (i == 0) {
                    head = new Node(scanner.nextInt());
                    last = head;
                } else {
                    Node key = new Node(scanner.nextInt());
                    last.next = key;
                    last = last.next;
                }
            }
            int m = scanner.nextInt();
            System.out.println(find(head,m));
        }
    }

方法二：用数组实现

import java.util.Scanner;
    
    public class Test {
        public static Integer find(int a[], int k) {
            if (k >a.length || k<=0){
                return null;
            }
            int i = 0;
            int j = k;
            while (j != a.length){
                i++;
                j++;
            }
            return a[i];
        }
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int []arr = new int[n];
            for (int i = 0;i<n;i++){
                arr[i] = scanner.nextInt();
            }
            int m = scanner.nextInt();
            System.out.println(find(arr,m));
        }
    }