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

#include <iostream>
using namespace std;

static struct ListNode {
    int val;
    ListNode* m_pNext;
    ListNode(int v) : val(v), m_pNext(nullptr) {}
};

// 定义单向链表类
static class SinglyLinkedList {
  private:
    ListNode* header;

  public:
    SinglyLinkedList() : header(nullptr) {
    }

    // 插入节点
    void insertNode(int val) {
        ListNode* newNode = new ListNode(val);
        ListNode* current = header;
        ListNode* prev = nullptr;

        if (header == nullptr) {
            header = newNode;
            return;
        }

        while (current != nullptr) {
            prev = current;
            current = current->m_pNext;
        }

        prev->m_pNext = newNode;
    }

    // 查找第 倒数第 k 个节点的值；
    void printNode(int k) {
        if (k < 1)
            return;

        // 双指针
        ListNode* current = header;
        ListNode* prev = header;

        // 让 一个指针先跑 k 个位置；；
        while (k--) {
            current = current->m_pNext;
        }
        // 再 两个同时移动，知道current 为 空，说明到了末尾；前一个指针就是倒数的位置了；
        while (current != nullptr) {
            prev = prev->m_pNext;
            current = current->m_pNext;
        }

        cout << prev->val << endl;

    }

    // 遍历 链表
    void traverse() {
        ListNode* current = header;

        while (current != nullptr) {
            cout << current->val << " ";
            current = current->m_pNext;
        }
        cout << endl;
    }


    // 析构函数
    ~SinglyLinkedList() {
        ListNode* current = header;
        ListNode* nextNode;
        while (current != nullptr) {
            nextNode = current->m_pNext;
            delete current;
            current = nextNode;
        }
    }
};

int main() {
    int n;

    while (cin >> n) {
        SinglyLinkedList s;
        while (n--) {
            int val;
            cin >> val;
            s.insertNode(val);
        }
        int k;
        cin >> k;
        s.printNode(k);
    }


    return 0;
}