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<<"th element from beginning towards head is "<<findKmiddleNode(head, k);

   return 0;
}

출력

2th element from beginning towards head is 7