C++でリンクリストの中央から先頭に向かってk番目のノードを検索します

この問題では、リンクリストと数kが与えられます。私たちのタスクは、ミドルからリンクリストのヘッドに向かってk番目のノードを見つけることです。

問題を理解するために例を見てみましょう。

入力： リンクリスト：4-> 2-> 7-> 1-> 9-> 12-> 8-> 10-> 5、k =2

出力： 7

説明：

中間ノードの値は9です。

中央から頭に向かって2番目のノードは7です。

ソリューションアプローチ

リンクリストの中央から先頭に向かってk番目の要素を見つける必要があります。このためには、リンクリストを最初から最後までトラバースしてサイズを見つけることにより、リンクリストのサイズを見つける必要があります。

中央から先頭に向かってK要素は、最初から（n / 2 + 1 --k）番目の要素です。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;

struct Node {
   int data;
   struct Node* next;
};

void pushNode(struct Node** head_ref, int new_data)
{
   struct Node* new_node = new Node;
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}

int findKmiddleNode(struct Node* head_ref, int k) {
   
   int n = 0;
   struct Node* counter = head_ref;
   while (counter != NULL) {
      n++;
      counter = counter->next;
   }
   int reqNode = ((n / 2 + 1) - k);

   if (reqNode <= 0)
      return -1;
     
   struct Node* current = head_ref;
   int count = 1;
   while (current != NULL) {
      if (count == reqNode)
         return (current->data);
      count++;
      current = current->next;
   }
}

int main()
{

   struct Node* head = NULL;
   int k = 2;
   pushNode(&head, 5);
   pushNode(&head, 10);
   pushNode(&head, 8);
   pushNode(&head, 12);
   pushNode(&head, 9);
   pushNode(&head, 1);
   pushNode(&head, 7);  
   pushNode(&head, 2);
   pushNode(&head, 4);

   cout<<k<<"th element from beginning towards head is "<<findKmiddleNode(head, k);

   return 0;
}

出力

2th element from beginning towards head is 7