题解 | #输出单向链表中倒数第k个结点#

import java.util.Scanner;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt(); // 输入链表结点个数
            ListNode dummy = new ListNode(0);
            ListNode tail = dummy;
            for (int i = 0; i < n; i++) {
                int val = scanner.nextInt(); // 输入链表的值
                ListNode node = new ListNode(val);
                tail.next = node;
                tail = node;
            }
            int k = scanner.nextInt(); // 输入k的值
            ListNode result = findKthToTail(dummy.next, k);
            if (result == null) {
                System.out.println("null");
            } else {
                System.out.println(result.val);
            }
        }
    }

    public static ListNode findKthToTail(ListNode head, int k) {
        if (head == null || k <= 0) {
            return null;
        }
        ListNode pAhead = head;
        ListNode pBehind = head;
        for (int i = 0; i < k - 1; i++) {
            if (pAhead.next != null) {
                pAhead = pAhead.next;
            } else {
                return null;
            }
        }
        while (pAhead.next != null) {
            pAhead = pAhead.next;
            pBehind = pBehind.next;
        }
        return pBehind;
    }
}

算法思路：

由于链表是单向链表，不能从后往前遍历，所以我们需要想办法从前往后遍历，同时记录两个指针，一个指针先走k-1步，然后第二个指针和第一个指针同时往后遍历，当第一个指针到达链表尾部时，第二个指针就指向了倒数第k个节点。

具体实现：

1. 定义两个指针，一个指针pAhead先走k-1步，另一个指针pBehind指向链表头部。
2. 从第k个节点开始，两个指针同时往后遍历，直到pAhead指向链表尾部，此时pBehind指向倒数第k个节点。

时间复杂度：O(n)，需要遍历一次链表。

空间复杂度：O(1)，只需要常数级别的额外空间存储两个指针。