Tìm nút mô-đun trong danh sách liên kết trong C ++

Trong bài toán này, chúng ta được cung cấp một danh sách liên kết đơn LL và một số k. Ourtask là Tìm nút mô-đun trong danh sách được liên kết.

Mô tả sự cố - chúng ta cần tìm nút cuối cùng của danh sách liên kết mà chỉ mục chia hết cho k tức là i% k ==0.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

ll = 3 -> 1 -> 9 -> 6 -> 8 -> 2, k = 4

Đầu ra

6

Giải thích

The element 6 has index 4, which is divisible by 4.

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tạo một bộ đếm để đếm các thành phần của danh sách được liên kết và lưu trữ nút mô-đun, tức là nút cho whichi% k ==0 và cập nhật cho tất cả các giá trị thỏa mãn điều kiện cho đến n.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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 == NULL)
      return NULL;
   int i = 1;
   Node* modNode = NULL;
   for (Node* currNode = head; currNode != NULL; currNode =
      currNode->next) {
         if (i % k == 0)
            modNode = currNode;
            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 != NULL)
      cout<<modularNode->data;
   else
   cout<<"Not found!";
   return 0;
}

Đầu ra

The Modular node of linked list is 6