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

#include <iostream>
using namespace std;

struct ListNode{
    int m_nKey;
    ListNode* m_pNext;
    ListNode():m_nKey(0),m_pNext(nullptr){};
    ListNode(int x):m_nKey(x),m_pNext(nullptr){};
};

// 之前我的代码还是记住了长度 违背题意  即使能ac

ListNode* getnode(ListNode* node, int& index)
{
    if(node==nullptr)
    {
        return nullptr;
    }
    
    ListNode* head = getnode(node->m_pNext, index);// 一直往后遍历

    if(--index==0)// 回溯时 减index 直到0 就是指定位置
    {
        return node;
    }
    else
    {
        return head; // 一直是nullptr
    }
}

int main() {
    int n, a;
    while (cin >> n) { // 注意 while 处理多个 case
        ListNode* head = new ListNode(); // 作为中间变量了
        ListNode* pre = head; // 固定的头结点
        while(n--)
        {
            cin >> a;
            ListNode* tmp = new ListNode(a);
            head->m_pNext = tmp;
            head = head->m_pNext;
        }
        int k;
        cin >> k;

        //递归地取到

        ListNode* ans = getnode(pre->m_pNext, k);

        if(ans==nullptr)
        {
            cout<<-1<<endl;
        }
        else
        {
            cout<<ans->m_nKey<<endl;
        }

    }
}
// 64 位输出请用 printf("%lld")