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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct ListNode {
    int m_nKey;
    ListNode *m_pNext;
    ListNode *_dummyHead;  // 虚拟头节点
    
    ListNode(int x) : m_nKey(x), m_pNext(nullptr) { }
};

void createList(ListNode *list, vector<int> val) {
    list->_dummyHead = new ListNode(0);  // 创建虚拟头节点，指向链表的第一个节点
    list->_dummyHead = list;
    for (int i = 0; i < val.size(); i++) {
        ListNode *ptr = new ListNode(0);  // 创建一个临时链表存放中间值
        ptr->m_nKey = val[i];
        ptr->m_pNext = nullptr;
        list->m_pNext = ptr;     // 将临时链表与目标链表相连接
        list = list->m_pNext;
    }
}

int lengthList(ListNode *list) {
    int len = 0;
    ListNode *cur = list->_dummyHead;
    while (cur->m_pNext != nullptr) {
        len++;
        cur = cur->m_pNext;
    }
    return len;
}

int findElement(ListNode *list, int k) {
    ListNode *ptr = list;
    while (k > 0 && ptr->m_pNext) {
        ptr = ptr->m_pNext;
        k--;
    }
    if (k == 0 && ptr != nullptr) {
        return ptr->m_nKey;
    } else {
        return -1;
    }
}

int main(){
    int n = 0;
    while (cin >> n) {
        vector<int> val;
        for (int i = 0; i < n; i++) {
            int temp = 0;
            cin >> temp;
            val.push_back(temp);
        }
        int k = 0;
        cin >> k;
        ListNode *list = new ListNode( 0 );
        createList(list, val);
        int len = lengthList(list);
        int m = len - k + 1;
        int res = findElement(list, m);
        if (res == -1) cout << -1 << endl;
        else cout << res << endl;
    }
    return 0;
}