Find the fractional (n/kth) node in the linked list
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
#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).