C++-এ সিংলি লিঙ্কড লিস্টে শেষ থেকে K-তম নোড বের করা

একটি সিংলি লিঙ্কড লিস্ট দেওয়া থাকলে, শেষ থেকে K-তম নোড বের করতে হবে।

ইনপুট

1→2→3→4→7→8→9, K = 4

আউটপুট

Node from the 4th Position is - 4

সমাধানের পদ্ধতি

দুই পয়েন্টার (slow, fast) ব্যবহার করে O(n) সময়ে সমাধান করা যায়।

• slow এবং fast দুটোই হেড থেকে শুরু করুন।
• fast-কে K ধাপ آگাড়ি সরান।
• এখন fast নাল না হয় পর্যন্ত slow এবং fast দুটোই এক ধাপ করে সরান।
• fast নাল হলে slow হবে K-তম নোড।

উদাহরণ

#include <iostream>
using namespace std;

class Node {
public:
    int data; Node* next;
    Node(int d) { data = d; next = NULL; }
};

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

void kthFromEnd(Node* head, int k) {
    Node *slow = head, *fast = head;
    for (int i = 0; i < k; i++) fast = fast->next;
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }
    cout << "Node from the " << k << "th position is " << slow->data << endl;
}

int main() {
    Node* head = NULL;
    insertAtHead(head, 2); insertAtHead(head, 4);
    insertAtHead(head, 5); insertAtHead(head, 6);
    insertAtHead(head, 7);
    kthFromEnd(head, 4);
    return 0;
}

আউটপুট

Node from the 4th position is: 6