Tìm nút thứ k từ Giữa đến Đầu danh sách được liên kết trong C ++

Trong bài toán này, chúng ta được cung cấp một danh sách liên kết và một số k. Nhiệm vụ của chúng ta là tìm nút thứ k từ Giữa về phía Đầu của Danh sách được Liên kết.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: danh sách liên kết:4 -> 2 -> 7 -> 1 -> 9 -> 12 -> 8 -> 10 -> 5, k =2

Đầu ra: 7

Giải thích:

Giá trị nút giữa là 9.

Nút thứ 2 từ giữa về phía đầu là 7.

Phương pháp tiếp cận giải pháp

Chúng ta cần tìm phần tử thứ k từ giữa danh sách liên kết về phía đầu. Để làm được điều này, chúng ta cần tìm kích thước của danh sách được liên kết bằng cách xem qua danh sách được liên kết từ đầu đến cuối và tìm kích thước.

K phần tử từ giữa về phía đầu là phần tử thứ (n / 2 + 1 - k) từ đầu.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

2th element from beginning towards head is 7