题意整理。

• 输入一个单向链表。
• 输出链表中倒数第k个节点。

方法一（双指针）

1.解题思路

• 首先进行特殊情况判断，如果k为0，直接返回空。
• 然后定义一个指针p指向head。让p先走k步，如果过程中走完链表，直接返回空。表示k大于链表长度。
• 当p走完k步后，让p和head一起往后走，直到p走完整个链表。head停留的位置即是倒数第k个节点。

图解展示：

2.代码实现

import java.util.Scanner;

//链表类
class ListNode{
    int val=0;
    ListNode next;
    public ListNode(int x){
        this.val=x;
    }
}
public class Main{
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //输入链表节点个数
            int n=sc.nextInt();
            //确定头节点
            ListNode head=new ListNode(sc.nextInt());
            ListNode p=head;
            //构造链表
            for(int i=0;i<n-1;i++){
                head.next=new ListNode(sc.nextInt());
                head=head.next;
            }
            //输入k的值
            int k=sc.nextInt();
            //寻找链表倒数第k个节点
            ListNode target=findK(p,k);
            if(target==null){
                System.out.println(0);   
            }
            else{
                System.out.println(target.val);   
            }           
            
        }      
    }
    
    //求倒数第k个节点
    public static ListNode findK(ListNode head,int k){
        //k为0，直接返回空
        if(k==0) return null;
        ListNode p=head;
        //p指针往前走k步
        for(int i=0;i<k;i++){
            if(p==null){
                return null;
            }
            p=p.next;
        }
        //然后让p和head一起往前走，由于head比p少走k步，所以head刚好到倒数第k个节点
        while(p!=null){
            p=p.next;
            head=head.next;
        }
        return head;
    }
    
}

3.复杂度分析

• 时间复杂度：最坏情况下，两个循环都执行完，p指针走了n步，head指针走了n-k步，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。

方法二（利用数组模拟）

1.解题思路

可以利用数组存储链表对应节点的值，由于数组可以利用索引直接确定某个位置的值，所以索引在n-k处对应的元素即是链表倒数第k个节点的值。

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //输入链表节点个数
            int n=sc.nextInt();
            //用于存储链表的值
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }
            //输入k的值
            int k=sc.nextInt();
            //数组索引为n-k的位置即是链表倒数第k个节点的值
            if(k==0){
                System.out.println(0);
            }
            else{
                System.out.println(arr[n-k]);
            }
        } 
    }
}

3.复杂度分析

• 时间复杂度：直接定位到n-k位置对应的元素，所以时间复杂度为$O(1)O(1)$。
• 空间复杂度：需要额外长度为n的数组，所以空间复杂度为$O(n)O(n)$。