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.
- Take two pointers temp and fractionalNode and initialize them with null and head respectively.
- 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 <bits/stdc++.h> /* 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 |
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.
leave a comment
0 Comments