Tìm node thứ K từ cuối danh sách liên kết đơn C++

Cho danh sách liên kết đơn, tìm node thứ K tính từ cuối. Ví dụ: 1→2→3→4→7→8→9, K=4 → node giá trị 4 (vị trí 4 từ cuối).

Phương pháp: Hai con trỏ (Fast & Slow)

• Khởi tạo slow và fast đều trỏ head.
• Di chuyển fast trước K bước.
• Sau đó di chuyển cả hai cùng lúc cho đến khi fast thành NULL.
• Lúc này slow trỏ đến node thứ K từ cuối.

Ví dụ mã nguồn

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

void insertAtHead(Node* &head, int d) {
    Node* n = new Node(d);
    n->next = head;
    head = n;
}

void printList(Node* head) {
    while (head) { cout << head->data << "-->"; head = head->next; }
    cout << endl;
}

void kthFromEnd(Node* head, int k) {
    Node *slow = head, *fast = head;
    for (int i=0;i

Kết quả
Node thu 4 tu cuoi: 6
Danh sách: 7→6→5→4→2. Node thứ 4 từ cuối là 6.