Find kth node from Middle towards Head of a Linked List in C++

In this problem, we are given a linked-list and a number k. Our task is to find kth node from Middle towards the Head of a Linked List. 

Let’s take an example to understand the problem, 

Input: linked-list : 4 -> 2 -> 7 -> 1 -> 9 -> 12 -> 8 -> 10 -> 5, k = 2

Output: 7

Explanation: 

Middle node value is 9.

The 2nd node from middle towards head is 7.

Solution Approach

We need to find kth element from the middle of the linked-list towards the beginning. For this we need to find the size of linked-list by traversing the linked-list from beginning to end and find size.

K element from the middle towards the start is the (n/2 + 1 - k)th element from the beginning.

Program to illustrate the working of our solution,

Example

Live Demo

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

Output

2th element from beginning towards head is 7