Giả sử có danh sách liên kết đơn và số k. Viết hàm tìm phần tử (n/k)th, n là số phần tử trong danh sách. Với số thập phân, lấy giá trị trần. Nếu danh sách 1, 2, 3, 4, 5, 6 và k = 2, kết quả là 3 vì n = 6, k = 2, in n/k th node là node thứ 3 là 3.
Để giải quyết, làm theo các bước:
- Lấy hai con trỏ temp và fracPoint, khởi tạo null và start.
- Với mỗi k nhảy của temp, làm một nhảy của fracPoint.
Ví dụ mã nguồn
#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; } Kết quả
List is: 1 2 3 4 5 Fractional node is 3