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 2^{nd}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.

If the linked list is

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 3^{rd}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

![](https://blog.prepbytes.com/wp-content/uploads/2021/08/Find-the-fractional-node-in-linked-list-1.png)

![](https://blog.prepbytes.com/wp-content/uploads/2021/08/Find-the-fractional-node-in-linked-list-2.png)

## 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) req_node = head; 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) { struct Node* head = newNode(3); head->next = newNode(5); head->next->next = newNode(7); head->next->next->next = newNode(9); head->next->next->next->next = newNode(11); int k = 2; printf("List is "); printList(head); struct Node* answer = fractionalNodes(head, k); printf("\nFractional node is "); printf("%d\n", answer->data); return 0; }

#includeusing 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; } Node* fractionalNodes(Node* head, int k) { 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) req_node = head; 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) { Node* head = newNode(3); head->next = newNode(5); head->next->next = newNode(7); head->next->next->next = newNode(9); head->next->next->next->next = newNode(11); int k = 2; printf("List is "); printList(head); Node* answer = fractionalNodes(head, k); printf("\nFractional node is "); printf("%d\n", answer->data); 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) fractionalNode = head; 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) { Node head = new Node(3); head.next = new Node(5); head.next.next = new Node(7); head.next.next.next = new Node(9); head.next.next.next.next = new Node(11); int k =2; System.out.print("List is "); printList(head); Node answer = fractionalNodes(head, k); System.out.println("Fractional node is "+answer.data); } }

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 def fractionalNodes(head, k): if (k <= 0 or head == None): return None fractionalNode = None i = 0 temp = head while (temp != None): if (i % k == 0): if (fractionalNode == None): fractionalNode = head 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__': head = newNode(3) head.next = newNode(5) head.next.next = newNode(7) head.next.next.next = newNode(9) head.next.next.next.next = newNode(11) k = 2 print("List is", end = ' ') printList(head) answer = fractionalNodes(head, k) print("\nFractional node is", end = ' ') print(answer.data)

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.