# Find the fractional (or n/k – th) node in linked list

### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this problem, we have been given a linked list and positive integer k. Our task is to write a function that accepts the head node of the linked list as a parameter and returns the value of the node present at (ceil(n/k))th position in the linked list.

Here, n is the count of the number of nodes in the linked list.

### Problem Statement Understanding

Let’s try to understand the problem with help of examples.

Suppose we are given a linked list

Now according to the problem statement we have to find the node at (ceil(n/k))th position in the linked list and return its value.

For the above given linked list n = 6, as there are 6 nodes in the linked list, so

• (ceil(n/k)) = (ceil(6/4)) = 2, it means that we have to return the value of 2nd node of the linked list as output.

Output: B
Explanation: We will return B in output as B is the value of (ceil(n/k))th node of the above given linked list. For the above linked list n = 9 (as there are 9 nodes in the linked list), then the value of (ceil(n/k)) is:

• (ceil(n/k)) = (ceil(9/3)) = 3, so we will return the value of the 3rd node of the linked list as output.

Output: C

Note: Here in this problem we are considering 1 based indexing.

##### Some more Examples

Input: Output: 5

Input: Output: 60

Input: Output: 18

Now I think from the above examples the problem is clear, and now we have to think how can we approach it.

### Approach 1

A simple approach is:

• First, loop through the linked list to find the count of number of nodes n present in the linked list.
• Then calculate the value of (ceil(n/k)).
• Now starting from the first node of the list traverse to this position given by (ceil(n/k)) and return the data of the node at this position.

Time Complexity: O(n), as we are traversing the complete length of the list.
Space Complexity: O(1)

This approach traverses the linked list 2 times. Let's try to think, can we do better than this? Can we find out the (ceil(n/k))th node of the linked list in one single traversal?

Let’s see the approach 2 to get the answers to the above questions.

### Approach 2

In this approach, we can get the required node by traversing the list once only. The complete algorithm for this approach is explained below.

### Algorithm

• If k<=0 or our head==NULL, then return NULL.
• We will take two pointers temp and req_node and initialize temp with head and req_node with NULL.
• For every k jumps of the temp pointer, we will make one jump of the req_node pointer.
• Now when temp will be at NULL, req_node will be at (ceil(n/k))th node of the linked list.
• Finally, we will return the req_node->data as output.

### Dry Run  ### Code Implementation:

```#include
using namespace std;

struct Node {
int data;
Node* next;
};

Node* newNode(int data)
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
{
if (k <= 0 || head == NULL)
return NULL;

Node* req_node = NULL;

int i = 0;
for (Node* temp = head; temp != NULL; temp = temp->next) {

if (i % k == 0) {

if (req_node == NULL)

else
req_node = req_node->next;
}
i++;
}
return req_node;
}

void printList(Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}

int main(void)
{
int k = 2;

printf("List is ");

printf("\nFractional node is ");