在 C++ 中查找链表中的分数 (或 n/k –th) 节点
假设我们有一个单链表和数字 k。我们需要编写一个函数来查找 (n/k)th 元素,其中 n 是链表中元素的数量。对于小数,我们将选择向上取整的值。因此,如果链表是 1、2、3、4、5、6,且 k = 2,那么输出将为 3,因为 n = 6,且 k = 2,那么我们将打印 n/k 第 n 个节点,即 6/2 的第 n 个节点 = 第 3 个节点即 3。
为了解决此问题,我们必须按照以下步骤进行操作 −
- 取两个名为 temp 和 fracPoint 的指针,分别将其初始化为 null 和 start。
- 对于 temp 指针的每次 k 次跳跃,进行 fracPoint 指针的一次跳跃。
示例
#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
广告