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

Find the fractional (n/k^th) 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

 #include<stdio.h>
 #include<stdlib.h>
 #include<math.h>
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node * t, * p;
 t = (struct node *)malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node * p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 //Function to find fractional node in the linked list
 struct node * fractionalNodes(struct node * temp, int k)
     {
         // Corner cases
 if (k <= 0 || temp == NULL)
 return NULL;
         // Traverse the given list
 intlen = 0;
 struct node * t;
 for(t = temp; t != NULL; t = t -> next)
                         len++;
 float fraction = (float)len/k;
 fraction = ceil(fraction);
 inti;
         t = temp;
 for(i = 1; i< fraction; i++)
         t = t -> next;
 return t;
     }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d -> ",t -> info);
                         t = t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 // Driver Function
 int main()
 {
 int k;
 printf("Enter the value of k:");
 scanf("%d",&k);
 add(1);
 add(2);
 add(4);
 add(5);
 add(9);
 add(10);
 add(12);
 add(15);
 add(13);
 printf("Given Linked List: \n");
 traverse(start);
 struct node * res;
 res = fractionalNodes(start, k);
 printf("Fraction node is:");
 printf("%d", res -> info);
 return 0;
 } 

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).