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.
This article is attributed to GeeksforGeeks.org
0
0
leave a comment
0 Comments