求链式线性表倒数第k项c++

链式线性表（Linked List）是一种动态数据结构，它的元素不存储在连续的位置上，而是通过节点间的链接来表示顺序。如果需要找到链表的倒数第k项，通常采用双指针策略。以下是使用C++的一个基本示例：

#include <iostream>

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

// 找到链表倒数第k项
ListNode* findKthToTail(ListNode* head, int k) {
    if (!head || !k) return nullptr; // 空链表或k值无效的情况

    ListNode* slow = head;   // 慢指针，每一步走一步
    ListNode* fast = head;    // 快指针，每一步走两步

    // 使用快慢指针找到链表长度
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 如果k大于链表长度，则返回nullptr
    if (k > 1 && !slow) return nullptr;

    // 缩短快指针到链表尾部，然后慢指针向前移动k-1步
    fast = slow;
    for (int i = 0; i < k - 1; ++i) {
        if (fast) fast = fast->next;
    }

    return fast;
}

// 示例演示如何使用
int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);

    int k = 2; // 查找倒数第二项
    ListNode* result = findKthToTail(head, k);
    if (result) std::cout << "倒数第 " << k << " 项是：" << result->val << "\n";
    else std::cout << "无法找到倒数第 " << k << " 项\n";

    return 0;
}

在这个例子中，`findKthToTail`函数接受链表头节点和整数k作为参数，通过控制两个指针的速度差来定位链表的特定位置。注意这个实现假设链表非空，并且k是非负的。