Select Page

Find the fractional (n/kth) node in the linked list

In this problem, we have given a singly linked list and a number k. Here we need to find the (n/k)th element where n is the number of elements in the linked list.

Note: In the case of decimals, ceil value will be considered.

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 -> 4 -> 1                   k = 3

Output:9

Since n is 7 and k is 3, we print ceil(7/3)th node, which is the 3rd node, i.e., 9.

Method:

This method first finds the length of the linked list, divides the length by the value of k, and then takes the ceiling value of it. After that, it will traverse the linked list till ceil(len/k) and return the appropriate node.

C program to find fractional node in a linked list

Output: –

Time Complexity:The time complexity of this method is O(1) which is constant time.

Space Complexity:The space complexity of the above method is O(1).