Linked List: Given a LL, find the kth node from middle towards the head

Problem Statement:

You are given a linked list and a number k.

You need to print the value of kth node from the middle of the list towards the head.

Position of middle node is (n/2)+1, where n is the total number of nodes in the list.

Example:

Input : List is 1->2->3->4->5->6->7
K= 2 
Output : 2

Solution Explanation:

Count the number of nodes.

Middle node will be at position (n/2) + 1/

Now print the node at (n/2 + 1 – kth) position from the head of the list

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std;

class Node 
{ 
    public:
    int data; 
    Node *next;

    Node (int new_value)
    {
        data = new_value;
        next = nullptr;
    }
}; 

int find_number_of_nodes(struct Node* head)
{
    int count = 0;  
    struct Node* current = head;  

    while (current != NULL) 
    {
        count++;
        current = current->next;
    }

    return count;
}
 

int solution(struct Node* head_ref, int k)
{

    int n = find_number_of_nodes(head_ref);
 
    int reqNode = ((n / 2 + 1) - k);
 
    if (reqNode <= 0) 
    {
        return -1;
    }
     else 
     {
        struct Node* current = head_ref;
 
        int count = 1;

        while (current != NULL) 
        {
            if (count == reqNode)
                return (current->data);
            count++;
            current = current->next;
        }
    }
        return -1;
}


int main() { 

    // Created linked list will be 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7  
    Node *headA = new Node(1); 
    headA->next = new Node(2);
    headA->next->next = new Node(3);
    headA->next->next->next = new Node(4);
    headA->next->next->next->next = new Node(5);
    headA->next->next->next->next->next = new Node(6);
    headA->next->next->next->next->next->next = new Node(7);

    int k = 2;

    cout<<solution(headA, k);
    
    return 0; 
} 

Output

2