给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

输入格式:

输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。

输出格式:

输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息NULL。

输入样例:

4 1 2 3 4 5 6 7 8 9 0 -1

输出样例:

7

#include <iostream>

using namespace std;

// 定义链表节点结构
struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
};

// 创建链表并返回头节点
ListNode* createLinkedList() {
    int value;
    ListNode* head = nullptr;
    ListNode* tail = nullptr;

    while (cin >> value && value >= 0) {
        ListNode* newNode = new ListNode(value);
        if (!head) {
            head = newNode;
        } else {
            tail->next = newNode;
        }
        tail = newNode;
    }

    return head;
}

// 查找链表的倒数第K个节点
int findKthFromEnd(ListNode* head, int K) {
    ListNode* fast = head;
    ListNode* slow = head;

    // 让fast指针先走K步
    for (int i = 0; i < K; ++i) {
        if (fast == nullptr) {
            return -1; // K大于链表长度
        }
        fast = fast->next;
    }

    // 同时移动slow和fast，直到fast到达链表末尾
    while (fast != nullptr) {
        slow = slow->next;
        fast = fast->next;
    }

    // slow现在指向倒数第K个节点
    return slow ? slow->data : -1;
}

// 主函数
int main() {
    int K;
    cin >> K;

    ListNode* head = createLinkedList();
    int result = findKthFromEnd(head, K);

    if (result == -1) {
        cout << "NULL" << endl;
    } else {
        cout << result << endl;
    }

    // 释放链表内存
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* next = current->next;
        delete current;
        current = next;
    }

    return 0;
}