  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

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

Last Updated on November 28, 2022 by Prepbytes This article discusses an important topic “find n/k th node in linked list”. “find n/k th node in linked list” is a good topic if you want to master the data structures. Linked List always remain the main bone of data structures and by conquering “find n/k th node in linked list” will make your linked list even more stronger and make it crystal clear to you.

## How To Find n/k Th Node In Linked List

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.

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 we can approach it.

## Approach 1 To Find n/k Th Node In Linked List

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 To Find n/k Th Node In Linked List: O(n), as we are traversing the complete length of the list.

Space Complexity To Find n/k Th Node In Linked List: 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 To Find n/k Th Node In Linked List

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 To Find n/k Th Node In Linked List

• 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 To Find n/k Th Node In Linked List

## Code Implementation To Find n/k Th Node In Linked List:

```#include
#include

struct Node {
int data;
struct Node* next;
};
struct Node* newNode(int x)
{
struct Node* node = malloc(sizeof(struct Node*));
node->data = x;
node->next = NULL;
return node;
}
struct Node* fractionalNodes(struct Node* head, int k)
{
if (k <= 0 || head == NULL)
return NULL;
struct Node* req_node = NULL;

int i = 0;
for (struct 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(struct 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 ");
return 0;
}
```
```#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 ");

return 0;
}
```
```public class FractionalNode
{
static class Node{
int data;
Node next;
Node (int data){
this.data = data;
}
}
static Node fractionalNodes(Node head, int k)
{
// Corner cases
if (k <= 0 || head == null)
return null;

Node fractionalNode = null;

// Traverse the given list
int i = 0;
for (Node temp = head; temp != null;temp = temp.next)
{
if (i % k == 0){
// First time we see a multiple of k
if (fractionalNode == null)
else
fractionalNode = fractionalNode.next;
}
i++;
}
return fractionalNode;
}
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data+" ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
int k =2;

System.out.print("List is ");

}
}
```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

def newNode(data):
new_node = Node(data)
new_node.data = data
new_node.next = None
return new_node

if (k <= 0 or head == None):
return None

fractionalNode = None
i = 0
while (temp != None):

if (i % k == 0):

if (fractionalNode == None):

else:
fractionalNode = fractionalNode.next

i = i + 1
temp = temp.next

return fractionalNode

def printList(node):
while (node != None):
print(node.data, end = ' ')
node = node.next

if __name__ == '__main__':
k = 2

print("List is", end = ' ')

print("\nFractional node is", end = ' ')
```

Output
List is 3 5 7 9 11
Fractional node is 7

**Time Complexity To Find n/k Th Node In Linked List:** O(n), as we are traversing the complete length of the list

This article discusses the question “Find n/k Th Node In Linked List” by two different approaches. Coding Questions like “Find n/k Th Node In Linked List” will always help in achieving the long term goals. Don’t stop here for practicing more questions of linked list, you can follow this link Linked List.

## FAQ

**1. How do you find the kth node from the end in a linked list?**
We will use the following property to find the kth node from the end. Kth node from end = (cnt-k+1)th node from the beginning. Let us store the value of cnt-k+1 in a variable ‘n’. Now traverse the linked list again and return the pointer to the ‘nth’ node.

**2. How do you find the common node between two linked lists?**
Compare every node of list A with every node of list B. If the node is a match then increment the count and return count after all the nodes get compared.

**3. Which companies have recently asked “Find n/k Th Node In Linked List” in their interviews?**
Tech Companies Samsung, Reliance JIO, TCS, Amazon, Accenture and Infosys have recently asked this question in the interview round for freshers.