Dada una lista enlazada, escriba una función que acepte el Node principal de la lista enlazada como parámetro y devuelva el valor del Node presente en (piso(sqrt(n)))ésima posición en la lista enlazada, donde n es la longitud de la lista enlazada o el número total de Nodes en la lista.
Ejemplos:
Input: 1->2->3->4->5->NULL Output: 2 Input : 10->20->30->40->NULL Output : 20 Input : 10->20->30->40->50->60->70->80->90->NULL Output : 30
Método simple : el método simple es encontrar primero el número total de Nodes presentes en la lista enlazada, luego encontrar el valor de piso (raíz cuadrada (n)) donde n es el número total de Nodes. A continuación, recorra desde el primer Node de la lista hasta esta posición y devuelva el Node a esta posición.
Este método atraviesa la lista enlazada 2 veces.
Enfoque optimizado : en este método, podemos obtener el Node requerido al recorrer la lista vinculada una sola vez. A continuación se muestra el algoritmo paso a paso para este enfoque.
- Inicialice dos contadores i y j ambos a 1 y un puntero sqrtn a NULL para recorrer hasta alcanzar la posición requerida.
- Comience a recorrer la lista usando el Node principal hasta llegar al último Node.
- Mientras atraviesa, verifique si el valor de j es igual a sqrt (i). Si el valor es igual, incremente tanto i como j y sqrtn hasta el punto sqrtn->siguiente; de lo contrario, incremente solo i.
- Ahora, cuando alcancemos el último Node de la lista, contendrá el valor de n, j contendrá el valor de sqrt (i) y sqrtn apuntará al Node en la posición j-ésima.
C++
// C++ program to find sqrt(n)'th node
// of a linked list
#include <bits/stdc++.h>
using namespace std;
// Linked list node
class Node
{
public:
int data;
Node* next;
};
// Function to get the sqrt(n)th
// node of a linked list
int printsqrtn(Node* head)
{
Node* sqrtn = NULL;
int i = 1, j = 1;
// Traverse the list
while (head!=NULL)
{
// check if j = sqrt(i)
if (i == j*j)
{
// for first node
if (sqrtn == NULL)
sqrtn = head;
else
sqrtn = sqrtn->next;
// increment j if j = sqrt(i)
j++;
}
i++;
head=head->next;
}
// return node's data
return sqrtn->data;
}
void print(Node* head)
{
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout<<endl;
}
// function to add a new node at the
// beginning of the list
void push(Node** head_ref, int new_data)
{
// allocate node
Node* new_node = new Node();
// put in the data
new_node->data = new_data;
// link the old list off the new node
new_node->next = (*head_ref);
// move the head to point to the new node
(*head_ref) = new_node;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
push(&head, 40);
push(&head, 30);
push(&head, 20);
push(&head, 10);
cout << "Given linked list is:";
print(head);
cout << "sqrt(n)th node is " << printsqrtn(head);
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program to find sqrt(n)'th node
// of a linked list
#include<stdio.h>
#include<stdlib.h>
// Linked list node
struct Node
{
int data;
struct Node* next;
};
// Function to get the sqrt(n)th
// node of a linked list
int printsqrtn(struct Node* head)
{
struct Node* sqrtn = NULL;
int i = 1, j = 1;
// Traverse the list
while (head!=NULL)
{
// check if j = sqrt(i)
if (i == j*j)
{
// for first node
if (sqrtn == NULL)
sqrtn = head;
else
sqrtn = sqrtn->next;
// increment j if j = sqrt(i)
j++;
}
i++;
head=head->next;
}
// return node's data
return sqrtn->data;
}
void print(struct Node* head)
{
while (head != NULL)
{
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
// function to add a new node at the
// beginning of the list
void push(struct Node** head_ref, int new_data)
{
// allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
// put in the data
new_node->data = new_data;
// link the old list off the new node
new_node->next = (*head_ref);
// move the head to point to the new node
(*head_ref) = new_node;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 40);
push(&head, 30);
push(&head, 20);
push(&head, 10);
printf("Given linked list is:");
print(head);
printf("sqrt(n)th node is %d ",printsqrtn(head));
return 0;
}
Java
// Java program to find sqrt(n)'th node
// of a linked list
class GfG
{
// Linked list node
static class Node
{
int data;
Node next;
}
static Node head = null;
// Function to get the sqrt(n)th
// node of a linked list
static int printsqrtn(Node head)
{
Node sqrtn = null;
int i = 1, j = 1;
// Traverse the list
while (head != null)
{
// check if j = sqrt(i)
if (i == j * j)
{
// for first node
if (sqrtn == null)
sqrtn = head;
else
sqrtn = sqrtn.next;
// increment j if j = sqrt(i)
j++;
}
i++;
head=head.next;
}
// return node's data
return sqrtn.data;
}
static void print(Node head)
{
while (head != null)
{
System.out.print( head.data + " ");
head = head.next;
}
System.out.println();
}
// function to add a new node at the
// beginning of the list
static void push( int new_data)
{
// allocate node
Node new_node = new Node();
// put in the data
new_node.data = new_data;
// link the old list off the new node
new_node.next = head;
// move the head to point to the new node
head = new_node;
}
/* Driver code*/
public static void main(String[] args)
{
/* Start with the empty list */
push( 40);
push( 30);
push( 20);
push( 10);
System.out.print("Given linked list is:");
print(head);
System.out.print("sqrt(n)th node is " +
printsqrtn(head));
}
}
// This code is contributed by prerna saini
Python3
# Python3 program to find sqrt(n)'th node
# of a linked list
# Node class
class Node:
# Function to initialise the node object
def __init__(self, data):
self.data = data
self.next = None
# Function to get the sqrt(n)th
# node of a linked list
def printsqrtn(head) :
sqrtn = None
i = 1
j = 1
# Traverse the list
while (head != None) :
# check if j = sqrt(i)
if (i == j * j) :
# for first node
if (sqrtn == None) :
sqrtn = head
else:
sqrtn = sqrtn.next
# increment j if j = sqrt(i)
j = j + 1
i = i + 1
head = head.next
# return node's data
return sqrtn.data
def print_1(head) :
while (head != None) :
print( head.data, end = " ")
head = head.next
print(" ")
# function to add a new node at the
# beginning of the list
def push(head_ref, new_data) :
# allocate node
new_node = Node(0)
# put in the data
new_node.data = new_data
# link the old list off the new node
new_node.next = (head_ref)
# move the head to point to the new node
(head_ref) = new_node
return head_ref
# Driver Code
if __name__=='__main__':
# Start with the empty list
head = None
head = push(head, 40)
head = push(head, 30)
head = push(head, 20)
head = push(head, 10)
print("Given linked list is:")
print_1(head)
print("sqrt(n)th node is ",
printsqrtn(head))
# This code is contributed by Arnab Kundu
C#
// C# program to find sqrt(n)'th node
// of a linked list
using System;
public class GfG
{
// Linked list node
class Node
{
public int data;
public Node next;
}
static Node head = null;
// Function to get the sqrt(n)th
// node of a linked list
static int printsqrtn(Node head)
{
Node sqrtn = null;
int i = 1, j = 1;
// Traverse the list
while (head != null)
{
// check if j = sqrt(i)
if (i == j * j)
{
// for first node
if (sqrtn == null)
sqrtn = head;
else
sqrtn = sqrtn.next;
// increment j if j = sqrt(i)
j++;
}
i++;
head=head.next;
}
// return node's data
return sqrtn.data;
}
static void print(Node head)
{
while (head != null)
{
Console.Write( head.data + " ");
head = head.next;
}
Console.WriteLine();
}
// function to add a new node at the
// beginning of the list
static void push( int new_data)
{
// allocate node
Node new_node = new Node();
// put in the data
new_node.data = new_data;
// link the old list off the new node
new_node.next = head;
// move the head to point to the new node
head = new_node;
}
/* Driver code*/
public static void Main(String[] args)
{
/* Start with the empty list */
push( 40);
push( 30);
push( 20);
push( 10);
Console.Write("Given linked list is:");
print(head);
Console.Write("sqrt(n)th node is " +
printsqrtn(head));
}
}
/* This code is contributed by 29AjayKumar */
Javascript
<script>
// JavaScript program to find sqrt(n)'th node
// of a linked list
// Linked list node
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
var head = null;
// Function to get the sqrt(n)th
// node of a linked list
function printsqrtn(head) {
var sqrtn = null;
var i = 1, j = 1;
// Traverse the list
while (head != null) {
// check if j = sqrt(i)
if (i == j * j) {
// for first node
if (sqrtn == null)
sqrtn = head;
else
sqrtn = sqrtn.next;
// increment j if j = sqrt(i)
j++;
}
i++;
head = head.next;
}
// return node's data
return sqrtn.data;
}
function print(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
document.write("<br/>");
}
// function to add a new node at the
// beginning of the list
function push(new_data) {
// allocate node
var new_node = new Node();
// put in the data
new_node.data = new_data;
// link the old list off the new node
new_node.next = head;
// move the head to point to the new node
head = new_node;
}
/* Driver code */
/* Start with the empty list */
push(40);
push(30);
push(20);
push(10);
document.write("Given linked list is:");
print(head);
document.write("sqrt(n)th node is " + printsqrtn(head));
// This code contributed by Rajput-Ji
</script>
Producción:
Given linked list is:10 20 30 40 sqrt(n)th node is 20
Análisis de Complejidad:
Complejidad temporal: O(n).
Complejidad espacial: O(1).
Este artículo es una contribución de Akshit Agarwal . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA