โปรแกรม C++ หาโหนดส่วนเศษ (n/k-th) ใน Linked List

สมมติว่าเรามี singly linked list และตัวเลข k เราต้องเขียนฟังก์ชันเพื่อหาองค์ประกอบที่ (n/k) โดยที่ n คือจำนวนองค์ประกอบในรายการ สำหรับทศนิยม เราจะเลือกค่า ceiling ดังนั้นถ้ารายการเป็น 1, 2, 3, 4, 5, 6 และ k = 2 ผลลัพธ์จะเป็น 3 เนื่องจาก n = 6 และ k = 2 เราจะพิมพ์โหนดที่ 6/2 = โหนดที่ 3 นั่นคือ 3

เพื่อแก้ปัญหานี้ เราต้องทำตามขั้นตอนเหล่านี้:

• ใช้ตัวชี้สองตัวชื่อ temp และ fracPoint เริ่มต้นเป็น null และ start ตามลำดับ
• สำหรับทุก k การกระโดดของตัวชี้ temp ให้ทำการกระโดดหนึ่งครั้งของตัวชี้ fracPoint

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

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

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

Node* fractionalNodes(Node* start, int k) {
    if (k <= 0 || start == NULL)
        return NULL;
    Node* fracPoint = NULL;
    int i = 0;
    for (Node* temp = start; temp != NULL; temp = temp->next) {
        if (i % k == 0) {
            if (fracPoint == NULL)
                fracPoint = start;
            else
                fracPoint = fracPoint->next;
        }
        i++;
    }
    return fracPoint;
}

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

int main(void) {
    Node* start = getNode(1);
    start->next = getNode(2);
    start->next->next = getNode(3);
    start->next->next->next = getNode(4);
    start->next->next->next->next = getNode(5);
    int k = 2;
    cout << "List is: ";
    printList(start);
    Node* answer = fractionalNodes(start, k);
    cout << "\nFractional node is " << answer->data;
}

ผลลัพธ์

List is: 1 2 3 4 5
Fractional node is 3