Tìm nút modular trong danh sách liên kết đơn trong C++

Giới thiệu

Cho danh sách liên kết đơn LL và số k. Tìm nút modular: nút cuối cùng có chỉ số (1-based) chia hết cho k (i % k == 0).

Ví dụ minh họa

Đầu vào

LL = 3 → 1 → 9 → 6 → 8 → 2, k = 4

Đầu ra

6

Giải thích

Nút 6 có chỉ số 4, chia hết cho 4.

Phương pháp giải

Duyệt danh sách một lần, đếm chỉ số i từ 1. Nếu i % k == 0, cập nhật kết quả = nút hiện tại. Trả về kết quả cuối cùng.

Chương trình minh họa

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* newNode(int data) {
    Node* new_node = new Node;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

Node* findModularNodeLL(Node* head, int k) {
    if (k <= 0 || !head) return NULL;
    int i = 1;
    Node* modNode = NULL;
    for (Node* curr = head; curr != NULL; curr = curr->next) {
        if (i % k == 0)
            modNode = curr;
        i++;
    }
    return modNode;
}

int main() {
    Node* head = newNode(3);
    head->next = newNode(1);
    head->next->next = newNode(9);
    head->next->next->next = newNode(6);
    head->next->next->next->next = newNode(8);
    head->next->next->next->next->next = newNode(2);
    
    int k = 4;
    Node* modularNode = findModularNodeLL(head, k);
    cout << "The Modular node of linked list is ";
    if (modularNode) cout << modularNode->data;
    else cout << "Not found!";
    return 0;
}

Đầu ra

The Modular node of linked list is 6