หา Modular Node ใน Linked List ด้วย C++

ภาพรวมปัญหา

ได้รับ Singly Linked List และ k หาโหนดสุดท้ายที่ index หาร k ลงตัว (i % k == 0)

ตัวอย่าง

อินพุต

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

เอาต์พุต

6

คำอธิบาย

Index 4 คือค่า 6 (3=1, 1=2, 9=3, 6=4)

วิธีแก้ปัญหา

เดินผ่าน Linked List นับ index เก็บโหนดล่าสุดที่ index % k == 0

โค้ดตัวอย่าง

#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* 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 != NULL)
        cout << modularNode->data;
    else
        cout << "Not found!";
    return 0;
}

เอาต์พุต

The Modular node of linked list is 6

สรุป

Single Pass O(N) ใช้พื้นที่ O(1) เก็บแค่โหนดล่าสุดที่ตรงเงื่อนไข