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

Given a singly linked list and a number k, write a function to find the (n/k)-th element, where n is the number of elements in the list. We need to consider ceil value in case of decimals.

Examples:

```Input : list = 1->2->3->4->5->6
k = 2
Output : 3
Since n = 6 and k = 2, we print (6/2)-th node
which is 3.

Input : list = 2->7->9->3->5
k = 3
Output : 7
Since n is 5 and k is 3, we print ceil(5/3)-th
node which is 2nd node, i.e., 7.
```

1. Take two pointers temp and fractionalNode and initialize them with null and head respectively.
2. For every k jumps of the temp pointer, make one jump of the fractionalNode pointer.

## C++

 `// C++ program to find fractional node in a linked list ` `#include ` ` `  `/* Linked list node */` `struct` `Node { ` `    ``int` `data; ` `    ``Node* next; ` `}; ` ` `  `/* Function to create a new node with given data */` `Node* newNode(``int` `data) ` `{ ` `    ``Node* new_node = ``new` `Node; ` `    ``new_node->data = data; ` `    ``new_node->next = NULL; ` `    ``return` `new_node; ` `} ` ` `  `/* Function to find fractional node in the linked list */` `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) { ` ` `  `        ``// For every k nodes, we move fractionalNode one ` `        ``// step ahead.  ` `        ``if` `(i % k == 0) { ` ` `  `            ``// First time we see a multiple of k ` `            ``if` `(fractionalNode == NULL) ` `                ``fractionalNode = head; ` ` `  `            ``else` `                ``fractionalNode = fractionalNode->next; ` `        ``} ` `        ``i++; ` `    ``} ` `    ``return` `fractionalNode; ` `} ` ` `  `// A utility function to print a linked list ` `void` `printList(Node* node) ` `{ ` `    ``while` `(node != NULL) { ` `        ``printf``(``"%d "``, node->data); ` `        ``node = node->next; ` `    ``} ` `    ``printf``(````" "````); ` `} ` ` `  `/* Driver program to test above function */` `int` `main(``void``) ` `{ ` `    ``Node* head = newNode(1); ` `    ``head->next = newNode(2); ` `    ``head->next->next = newNode(3); ` `    ``head->next->next->next = newNode(4); ` `    ``head->next->next->next->next = newNode(5); ` `    ``int` `k = 2; ` ` `  `    ``printf``(``"List is "``); ` `    ``printList(head); ` ` `  `    ``Node* answer = fractionalNodes(head, k); ` `    ``printf``(````" Fractional node is "````); ` `    ``printf``(````"%d "````, answer->data); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to find fractional node in ` `// a linked list ` `public` `class` `FractionalNodell ` `{ ` `    ``/* Linked list node */` `    ``static` `class` `Node{ ` `        ``int` `data; ` `        ``Node next; ` ` `  `        ``//Constructor ` `        ``Node (``int` `data){ ` `            ``this``.data = data; ` `        ``} ` `    ``} ` ` `  `    ``/* Function to find fractional node in the ` `       ``linked list */` `    ``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){ ` ` `  `            ``// For every k nodes, we move ` `            ``// fractionalNode one step ahead. ` `            ``if` `(i % k == ``0``){ ` ` `  `                ``// First time we see a multiple of k ` `                ``if` `(fractionalNode == ``null``) ` `                    ``fractionalNode = head; ` `                ``else` `                    ``fractionalNode = fractionalNode.next; ` `            ``} ` `            ``i++; ` `        ``} ` `        ``return` `fractionalNode; ` `    ``} ` ` `  `    ``// A utility function to print a linked list ` `    ``static` `void` `printList(Node node) ` `    ``{ ` `        ``while` `(node != ``null``) ` `        ``{ ` `            ``System.out.print(node.data+``" "``); ` `            ``node = node.next; ` `        ``} ` `        ``System.out.println(); ` `    ``} ` ` `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `main(String[] args) { ` `        ``Node head = ``new` `Node(``1``); ` `        ``head.next = ``new` `Node(``2``); ` `        ``head.next.next = ``new` `Node(``3``); ` `        ``head.next.next.next = ``new` `Node(``4``); ` `        ``head.next.next.next.next = ``new` `Node(``5``); ` `        ``int` `k =``2``; ` ` `  `        ``System.out.print(``"List is "``); ` `        ``printList(head); ` ` `  `        ``Node answer = fractionalNodes(head, k); ` `        ``System.out.println(``"Fractional node is "``+ ` `                                      ``answer.data); ` `    ``} ` `} ` `// This code is contributed by Sumit Ghosh `

## C#

 `// C# program to find fractional node in ` `// a linked list ` `using` `System; ` ` `  `public` `class` `FractionalNodell ` `{ ` `    ``/* Linked list node */` `    ``public` `class` `Node ` `    ``{ ` `        ``public` `int` `data; ` `        ``public` `Node next; ` ` `  `        ``//Constructor ` `        ``public` `Node (``int` `data) ` `        ``{ ` `            ``this``.data = data; ` `        ``} ` `    ``} ` ` `  `    ``/* Function to find fractional node in the ` `    ``linked list */` `    ``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) ` `        ``{ ` ` `  `            ``// For every k nodes, we move ` `            ``// fractionalNode one step ahead. ` `            ``if` `(i % k == 0) ` `            ``{ ` ` `  `                ``// First time we see a multiple of k ` `                ``if` `(fractionalNode == ``null``) ` `                    ``fractionalNode = head; ` `                ``else` `                    ``fractionalNode = fractionalNode.next; ` `            ``} ` `            ``i++; ` `        ``} ` `        ``return` `fractionalNode; ` `    ``} ` ` `  `    ``// A utility function to print a linked list ` `    ``static` `void` `printList(Node node) ` `    ``{ ` `        ``while` `(node != ``null``) ` `        ``{ ` `            ``Console.Write(node.data+``" "``); ` `            ``node = node.next; ` `        ``} ` `        ``Console.WriteLine(); ` `    ``} ` ` `  `    ``/* Driver code */` `    ``public` `static` `void` `Main(String[] args)  ` `    ``{ ` `        ``Node head = ``new` `Node(1); ` `        ``head.next = ``new` `Node(2); ` `        ``head.next.next = ``new` `Node(3); ` `        ``head.next.next.next = ``new` `Node(4); ` `        ``head.next.next.next.next = ``new` `Node(5); ` `        ``int` `k =2; ` ` `  `        ``Console.Write(``"List is "``); ` `        ``printList(head); ` ` `  `        ``Node answer = fractionalNodes(head, k); ` `        ``Console.WriteLine(``"Fractional node is "``+ ` `                                    ``answer.data); ` `    ``} ` `} ` ` `  `// This code is contributed by Rajput-Ji `

/div>

Output:

```List is 1 2 3 4 5
Fractional node is 3
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

## tags:

Linked List Fraction Linked List

code

load comments