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

考察单链表的构造与遍历。

递归

#include <bits/stdc++.h>

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

using namespace std;

int k;
int cnt;
vector<int> nums;
ListNode* res;


void dfs2(ListNode* node)
{
    if (node == nullptr)
        return;
    dfs2(node->m_pNext);
    if (++cnt == k) {
        res = node;
    }
}

ListNode* dfs1(int idx)
{
    if (idx == nums.size()) return nullptr;
    ListNode* node = new ListNode(nums[idx]);
    node->m_pNext = dfs1(idx + 1);
    return node;
}

int main()
{
    int amount;
    for (; cin >> amount;)
    {
        nums = {};
        res = nullptr;
        cnt = 0;
        for (; amount--;)
        {
            int num;
            cin >> num;
            nums.push_back(num);
        }
        cin >> k;
        if (!amount || !k) {
            cout << 0 << endl;
            continue;
        }
        ListNode* pHead = dfs1(0);

        res = new ListNode(-1);
        dfs2(pHead);
        cout << res->m_nKey << endl;
    }

    return 0;
}