C++의 연결 목록에서 분수(또는 n/k – th) 노드 찾기

단일 연결 목록과 숫자 k가 있다고 가정합니다. (n/k)번째 요소를 찾는 함수를 작성해야 합니다. 여기서 n은 목록의 요소 수입니다. 소수의 경우 상한값을 선택합니다. 따라서 목록이 1, 2, 3, 4, 5, 6 및 k =2와 같으면 출력은 n =6 및 k =2이므로 3이 되고 n/k 번째 노드를 인쇄하므로 6/ 2번째 노드 =3번째 노드인 3.

이 문제를 해결하려면 아래와 같은 몇 가지 단계를 따라야 합니다.

• temp 및 fracPoint라는 두 개의 포인터를 가져온 다음 각각 null 및 start로 초기화합니다.
• 모든 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