方法一：顺序查找

具体做法

最简单直接的方法即为顺序查找，假设当前链表的长度为 n，则我们知道链表的倒数第 k 个节点即为正数第 n - k 个节点，此时我们只需要顺序遍历到链表的第 n - k个节点即为倒数第 k个节点。

我们首先求出链表的长度 n，然后顺序遍历到链表的第 n - k个节点返回即可。

Java代码

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) {
        int n = 0;
        ListNode node = null;
      //记录有多少节点
        for (node = head; node != null; node = node.next) {
            n++;
        }
      //找倒数第k个
        for (node = head; n > k; n--) {
            node = node.next;
        }

        return node;
    }
}

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

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中 $nn$为链表的长度。需要两次遍历。
• 空间复杂度：$O(1)O(1)$。

方法二：快慢指针

具体方法

快慢指针的思想。将第一个指针 fast 指向链表的第k+1 个节点，第二个指针 slow 指向链表的第一个节点，此时指针fast 与slow 二者之间刚好间隔 k 个节点。此时两个指针同步向后走，当第一个指针fast 走到链表的尾部空节点时，则此时slow 指针刚好指向链表的倒数第k个节点。

首先将 fast 指向链表的头节点，然后向后走k 步，则此时fast 指针刚好指向链表的第k+1 个节点。

首先将slow 指向链表的头节点，同时slow 与fast 同步向后走，当 fast 指针指向链表的尾部空节点时，则此时返回 slow 所指向的节点即可。

Java代码

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;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表的长度。我们使用快慢指针，只需要一次遍历即可，复杂度为 $O(n)O(n)$。
• 空间复杂度：$O(1)O(1)$。