题解 | #输出单向链表中倒数第k个结点#C++双指针巧妙

#include <iostream>
using namespace std;
struct ListNode {
    int value;
    ListNode* next;
  //要初始化结点的值，否则会导致未定义行为，应为node->next可能指向任意内存地址
    ListNode(int x) : value(x), next(nullptr) {}
};
void OutputLaskKNode(ListNode* head, int k) {
  //如果头结点为空或者输入的k的数值小于等于0，直接return
  if (head == nullptr || k <= 0) return; 
	//初始化p1,p2结点，都指向head
    ListNode* p1 = head;
    ListNode* p2 = head;
//先让p1移动k个结点，如果p1到达链表末尾，说明k太大，直接return
    for (int i = 0; i < k; i++) {
        if (p1 == nullptr) return;
        p1 = p1->next;
    }
//然后p1跟p2同时移动，直到p1到达链表末尾(p1为最后一个结点的下一个结点 nullptr)，因为p1跟p2直接相隔3个 p1 - p2 = 3;所以，此时p2所在的位置就是倒数第k个位置
    while (p1 != nullptr) {
        p1 = p1->next;
        p2 = p2->next;
    }

    cout << p2->value << endl;
}
int main() {
    while (true) {
        int numOfNode;
        cin >> numOfNode;
	  //一定要有这一句，不然最后一组输入数据会重复执行
        if (cin.fail()) break;
        ListNode* head = nullptr;
        ListNode* tail = nullptr;

        for (int i = 0; i < numOfNode; i++) {
            int nodeValue;
            cin >> nodeValue;;
            ListNode* newNode = new ListNode(nodeValue);
            if (head == nullptr) {
                head = newNode;
                tail = newNode;
            } else {
                tail->next = newNode;
                tail = newNode;
            }
        }

        int k;
        cin >> k;
	  //这里也要加上输入失败，跳出循环
        if (cin.fail()) break;
        OutputLaskKNode(head, k);

        ListNode* current = head;
        while (current != nullptr) {
            ListNode* next = current->next;
            delete current;
            current = next;
        }

        head = nullptr;
    }

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