在 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

更新于:19-Dec-2019

188 次浏览

开启您的 职业

完成课程认证

开始学习
广告