Encuentre el Node fraccional (o n/k – th) en la lista enlazada

Dada una lista enlazada individualmente y un número k, escriba una función para encontrar el (n/k)-ésimo elemento, donde n es el número de elementos en la lista. Necesitamos considerar el valor límite en caso de decimales.

Ejemplos: 

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.

1. Tome dos punteros temp y fraccionalNode e inicialícelos con nulo y cabeza respectivamente.
2. Por cada k saltos del puntero temporal, haga un salto del puntero del Node fraccionario.

Implementación:

// 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("\n");
}
 
/* 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("\nFractional node is ");
    printf("%d\n", answer->data);
 
    return 0;
}

// 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

# Python3 program to find fractional node
# in a linked list
import math
 
# Linked list node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Function to create a new node
# with given data
def newNode(data):
    new_node = Node(data)
    new_node.data = data
    new_node.next = None
    return new_node
 
# Function to find fractional node
# in the linked list
def fractionalNodes(head, k):
     
    # Corner cases
    if (k <= 0 or head == None):
        return None
 
    fractionalNode = None
 
    # Traverse the given list
    i = 0
    temp = head
    while (temp != None):
         
        # For every k nodes, we move
        # fractionalNode one step ahead.
        if (i % k == 0):
 
            # First time we see a multiple of k
            if (fractionalNode == None):
                fractionalNode = head
 
            else:
                fractionalNode = fractionalNode.next
 
        i = i + 1
        temp = temp.next
 
    return fractionalNode
 
# A utility function to print a linked list
def printList(node):
    while (node != None):
        print(node.data, end = ' ')
        node = node.next
 
# Driver Code
if __name__ == '__main__':
    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)
    k = 2
 
    print("List is", end = ' ')
    printList(head)
 
    answer = fractionalNodes(head, k)
    print("\nFractional node is", end = ' ')
    print(answer.data)
 
# This code is contributed by Srathore

// 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

<script>
 
// JavaScript program to find fractional node in
// a linked list
 
    /* Linked list node */
     class Node {
            constructor(val) {
                this.data = val;
                this.next = null;
            }
        }
 
    /*
     * Function to find fractional node in the linked list
     */
    function fractionalNodes(head , k) {
        // Corner cases
        if (k <= 0 || head == null)
            return null;
 
        var fractionalNode = null;
 
        // Traverse the given list
        var i = 0;
        for (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
    function printList(node) {
        while (node != null) {
            document.write(node.data + " ");
            node = node.next;
        }
        document.write();
    }
 
    /* Driver program to test above function */
     
        var 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);
        var k = 2;
 
        document.write("List is ");
        printList(head);
 
        var answer = fractionalNodes(head, k);
        document.write("<br/>Fractional node is " + answer.data);
 
// This code contributed by Rajput-Ji
 
</script>

List is 1 2 3 4 5 

Fractional node is 3

Análisis de Complejidad

• Complejidad de tiempo: O(n)
• Complejidad del espacio: O(1)

Este artículo es una contribución de Prakriti Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.