在C ++中从中间到链接列表的开头查找第k个节点

在这个问题上，我们得到一个链表和一个数字k。我们的任务是找到从中间到链表头的第k个节点。 

让我们举个例子来了解这个问题， 

输入： 链表：4-> 2-> 7-> 1-> 9-> 12-> 8-> 10-> 5，k = 2

输出：  7

解释： 

中间节点值为9。

从中间到头部的第二个节点是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<<"t从头到头的h元素是 "<<findKmiddleNode(head, k);

   return 0;
}

2t从头到头的h元素是 7