Dada una lista enlazada y un número n, escriba una función que devuelva el valor en el Node n desde el final de la lista enlazada.
Por ejemplo, si la entrada está debajo de la lista y n = 3, entonces la salida es «B»
Método 1 (Usar la longitud de la lista enlazada)
1) Calcular la longitud de la Lista enlazada. Sea la longitud len.
2) Imprima el (len – n + 1) Node desde el principio de la lista enlazada.
Concepto de puntero doble: el primer puntero se usa para almacenar la dirección de la variable y el segundo puntero se usa para almacenar la dirección del primer puntero. Si deseamos cambiar el valor de una variable por una función, le pasamos un puntero. Y si deseamos cambiar el valor de un puntero (es decir, debería comenzar a apuntar a otra cosa), pasamos el puntero a un puntero.
A continuación se muestra la implementación del enfoque anterior:
C++14
// Simple C++ program to find n'th node from end
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to get the nth node from
the last of a linked list*/
void printNthFromLast(struct Node* head, int n)
{
int len = 0, i;
struct Node* temp = head;
// count the number of nodes in Linked List
while (temp != NULL) {
temp = temp->next;
len++;
}
// check if value of n is not
// more than length of the linked list
if (len < n)
return;
temp = head;
// get the (len-n+1)th node from the beginning
for (i = 1; i < len - n + 1; i++)
temp = temp->next;
cout << temp->data;
return;
}
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct 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 Code
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
// create linked 35->15->4->20
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 35);
printNthFromLast(head, 4);
return 0;
}
C
// Simple C++ program to find n'th node from end
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
typedef struct Node {
int data;
struct Node* next;
}Node;
/* Function to get the nth node from the last of a linked list*/
void printNthFromLast(Node* head, int n)
{
int len = 0, i;
Node* temp = head;
// count the number of nodes in Linked List
while (temp != NULL) {
temp = temp->next;
len++;
}
// check if value of n is not
// more than length of the linked list
if (len < n)
return;
temp = head;
// get the (len-n+1)th node from the beginning
for (i = 1; i < len - n + 1; i++)
temp = temp->next;
printf("%d",temp->data);
return;
}
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = (Node *)malloc(sizeof(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 Code
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
// create linked 35->15->4->20
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 35);
printNthFromLast(head, 4);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Simple Java program to find n'th node from end of linked list
class LinkedList {
Node head; // head of the list
/* Linked List node */
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Function to get the nth node from the last of a
linked list */
void printNthFromLast(int n)
{
int len = 0;
Node temp = head;
// 1) count the number of nodes in Linked List
while (temp != null) {
temp = temp.next;
len++;
}
// check if value of n is not more than length of
// the linked list
if (len < n)
return;
temp = head;
// 2) get the (len-n+1)th node from the beginning
for (int i = 1; i < len - n + 1; i++)
temp = temp.next;
System.out.println(temp.data);
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver program to test above methods */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);
llist.printNthFromLast(4);
}
} // This code is contributed by Rajat Mishra
Python3
# Simple Python3 program to find
# n'th node from end
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# createNode and make linked list
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Function to get the nth node from
# the last of a linked list
def printNthFromLast(self, n):
temp = self.head # used temp variable
length = 0
while temp is not None:
temp = temp.next
length += 1
# print count
if n > length: # if entered location is greater
# than length of linked list
print('Location is greater than the' +
' length of LinkedList')
return
temp = self.head
for i in range(0, length - n):
temp = temp.next
print(temp.data)
# Driver Code
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(35)
llist.printNthFromLast(4)
# This code is contributed by Yogesh Joshi
C#
// C# program to find n'th node from end of linked list
using System;
public class LinkedList
{
public Node head; // head of the list
/* Linked List node */
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
/* Function to get the nth node from the last of a
linked list */
void printNthFromLast(int n)
{
int len = 0;
Node temp = head;
// 1) count the number of nodes in Linked List
while (temp != null)
{
temp = temp.next;
len++;
}
// check if value of n is not more than length of
// the linked list
if (len < n)
return;
temp = head;
// 2) get the (len-n+1)th node from the beginning
for (int i = 1; i < len - n + 1; i++)
temp = temp.next;
Console.WriteLine(temp.data);
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver code */
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);
llist.printNthFromLast(4);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Simple Javascript program to find n'th node from end of linked list
/* Linked List node */
class Node {
constructor(d)
{
this.data = d;
this.next = null;
}
}
/* Function to get the nth node from the last of a
linked list */
class LinkedList
{
constructor(d){
this.head = d;
}
printNthFromLast(n)
{
let len = 0;
let temp = this.head;
// 1) count the number of nodes in Linked List
while (temp != null) {
temp = temp.next;
len++;
}
// check if value of n is not more than length of
// the linked list
if (len < n)
return;
temp = this.head;
// 2) get the (len-n+1)th node from the beginning
for (let i = 1; i < len - n + 1; i++)
temp = temp.next;
document.write(temp.data);
}
/* Inserts a new Node at front of the list. */
push(new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
let new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = this.head;
/* 4. Move the head to point to new Node */
this.head = new_node;
}
}
/*Driver program to test above methods */
let llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);
llist.printNthFromLast(4);
// This code is contributed by Saurabh Jaiswal
</script>
Producción
35
Complejidad temporal: O(n) donde n es el tamaño de la lista enlazada
Espacio Auxiliar: O(1)
A continuación se muestra un código C recursivo para el mismo método. Gracias a Anuj Bansal por proporcionar el siguiente código.
Implementación:
C++
void printNthFromLast(struct Node* head, int n)
{
int i = 0;
if (head == NULL)
return;
printNthFromLast(head->next, n);
if (++i == n)
cout<<head->data;
}
C
void printNthFromLast(struct Node* head, int n)
{
static int i = 0;
if (head == NULL)
return;
printNthFromLast(head->next, n);
if (++i == n)
printf("%d", head->data);
}
Java
static void printNthFromLast(Node head, int n)
{
int i = 0;
if (head == null)
return;
printNthFromLast(head.next, n);
if (++i == n)
System.out.print(head.data);
}
// This code is contributed by rutvik_56.
Python3
def printNthFromLast(head, n): i = 0 if (head == None) return printNthFromLast(head.next, n); i+=1 if (i == n): print(head.data) # This code is contributed by sunils0ni.
C#
static void printNthFromLast(Node head, int n)
{
static int i = 0;
if (head == null)
return;
printNthFromLast(head.next, n);
if (++i == n)
Console.Write(head.data);
}
// This code is contributed by pratham76.
Javascript
<script>
function printNthFromLast(head , n)
{
function i = 0;
if (head == null)
return;
printNthFromLast(head.next, n);
if (++i == n)
document.write(head.data);
}
// This code is contributed by gauravrajput1
</script>
Complejidad de tiempo: O(n) donde n es la longitud de la lista enlazada.
Espacio auxiliar: O(n) para pila de llamadas
Método 2 (Usar dos punteros)
Mantener dos punteros: puntero de referencia y puntero principal. Inicialice tanto los punteros de referencia como los principales en head. Primero, mueva el puntero de referencia a n Nodes desde la cabeza. Ahora mueva ambos punteros uno por uno hasta que el puntero de referencia llegue al final. Ahora el puntero principal apuntará al Node n desde el final. Devuelve el puntero principal.
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find n-th node
// from the end of the linked list.
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
node* next;
node(int val)
{
data = val;
next = NULL;
}
};
struct llist {
node* head;
llist() { head = NULL; }
// insert operation at the beginning of the list.
void insertAtBegin(int val)
{
node* newNode = new node(val);
newNode->next = head;
head = newNode;
}
// finding n-th node from the end.
void nthFromEnd(int n)
{
// create two pointers main_ptr and ref_ptr
// initially pointing to head.
node* main_ptr = head;
node* ref_ptr = head;
// if list is empty, return
if (head == NULL) {
cout << "List is empty" << endl;
return;
}
// move ref_ptr to the n-th node from beginning.
for (int i = 1; i < n; i++) {
ref_ptr = ref_ptr->next;
if (ref_ptr == NULL) {
cout << n
<< " is greater than no. of nodes in "
"the list"
<< endl;
return;
}
}
// move ref_ptr and main_ptr by one node until
// ref_ptr reaches end of the list.
while (ref_ptr != NULL && ref_ptr->next != NULL) {
ref_ptr = ref_ptr->next;
main_ptr = main_ptr->next;
}
cout << "Node no. " << n
<< " from end is: " << main_ptr->data << endl;
}
void displaylist()
{
node* temp = head;
while (temp != NULL) {
cout << temp->data << "->";
temp = temp->next;
}
cout << "NULL" << endl;
}
};
int main()
{
llist ll;
for (int i = 60; i >= 10; i -= 10)
ll.insertAtBegin(i);
ll.displaylist();
for (int i = 1; i <= 7; i++)
ll.nthFromEnd(i);
return 0;
}
// This code is contributed by sandeepkrsuman.
Java
// Java program to find n'th
// node from end using slow and
// fast pointers
class LinkedList
{
Node head; // head of the list
/* Linked List node */
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Function to get the
nth node from end of list */
void printNthFromLast(int n)
{
Node main_ptr = head;
Node ref_ptr = head;
int count = 0;
if (head != null)
{
while (count < n)
{
if (ref_ptr == null)
{
System.out.println(n
+ " is greater than the no "
+ " of nodes in the list");
return;
}
ref_ptr = ref_ptr.next;
count++;
}
if(ref_ptr == null)
{
if(head != null)
System.out.println("Node no. " + n +
" from last is " +
head.data);
}
else
{
while (ref_ptr != null)
{
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
System.out.println("Node no. " + n +
" from last is " +
main_ptr.data);
}
}
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver program to test above methods */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);
llist.printNthFromLast(4);
}
}
// This code is contributed by Rajat Mishra
Python3
# Python program to find n'th node from end using slow
# and fast pointer
# Node class
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def printNthFromLast(self, n):
main_ptr = self.head
ref_ptr = self.head
count = 0
if(self.head is not None):
while(count < n ):
if(ref_ptr is None):
print ("% d is greater than the no. pf nodes in list" %(n))
return
ref_ptr = ref_ptr.next
count += 1
if(ref_ptr is None):
self.head = self.head.next
if(self.head is not None):
print("Node no. % d from last is % d "
%(n, main_ptr.data))
else:
while(ref_ptr is not None):
main_ptr = main_ptr.next
ref_ptr = ref_ptr.next
print ("Node no. % d from last is % d "
%(n, main_ptr.data))
if __name__ == '__main__':
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(35)
llist.printNthFromLast(4)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to find n'th node from end using slow and
// fast pointerspublic
using System;
public class LinkedList
{
Node head; // head of the list
/* Linked List node */
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
/* Function to get the nth node from end of list */
void printNthFromLast(int n)
{
Node main_ptr = head;
Node ref_ptr = head;
int count = 0;
if (head != null)
{
while (count < n)
{
if (ref_ptr == null)
{
Console.WriteLine(n + " is greater than the no "
+ " of nodes in the list");
return;
}
ref_ptr = ref_ptr.next;
count++;
}
if(ref_ptr == null)
{
head = head.next;
if(head != null)
Console.WriteLine("Node no. " +
n + " from last is " +
main_ptr.data);
}
else
{
while (ref_ptr != null)
{
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
Console.WriteLine("Node no. " +
n + " from last is " +
main_ptr.data);
}
}
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver code */
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);
llist.printNthFromLast(4);
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// javascript program to find n'th
// node from end using slow and
// fast pointers
var head; // head of the list
/* Linked List node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/*
* Function to get the nth node from end of list
*/
function printNthFromLast(n)
{
var main_ptr = head;
var ref_ptr = head;
var count = 0;
if (head != null) {
while (count < n) {
if (ref_ptr == null) {
document.write(n + " is greater than the no " +
" of nodes in the list");
return;
}
ref_ptr = ref_ptr.next;
count++;
}
if (ref_ptr == null) {
if (head != null)
document.write("Node no. " + n + " from last is " + head.data);
} else {
while (ref_ptr != null) {
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
document.write("Node no. " + n + " from last is " + main_ptr.data);
}
}
}
/* Inserts a new Node at front of the list. */
function push(new_data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Driver program to test above methods */
push(20);
push(4);
push(15);
push(35);
printNthFromLast(4);
// This code is contributed by Rajput-Ji
</script>
Producción
10->20->30->40->50->60->NULL Node no. 1 from end is: 60 Node no. 2 from end is: 50 Node no. 3 from end is: 40 Node no. 4 from end is: 30 Node no. 5 from end is: 20 Node no. 6 from end is: 10 7 is greater than no. of nodes in the list
Complejidad de tiempo: O(n) donde n es la longitud de la lista enlazada.
Espacio auxiliar: O(1)
Escriba comentarios si encuentra que los códigos/algoritmos anteriores son incorrectos o encuentra otras formas de resolver el mismo problema.
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