Dada una lista enlazada , muestra la lista enlazada al revés sin usar recursividad, pila o modificaciones a la lista dada.
Ejemplos:
Input : 1->2->3->4->5->NULL Output :5->4->3->2->1->NULL Input :10->5->15->20->24->NULL Output :24->20->15->5->10->NULL
A continuación se muestran diferentes soluciones que ahora están permitidas aquí, ya que no podemos usar espacio adicional y modificar la lista.
1) Solución recursiva para imprimir al revés una lista enlazada . Requiere espacio adicional.
2) Lista enlazada inversa y luego imprimir. Esto requiere modificaciones a la lista original.
3) Solución basada en pila para imprimir la lista vinculada inversamente . Empuje todos los Nodes uno por uno a una pila. Luego, uno por uno, saque los elementos de la pila e imprímalos. Esto también requiere espacio adicional.
Algoritmos:
1) Find n = count nodes in linked list. 2) For i = n to 1, do following. Print i-th node using get n-th node function
C++
// C/C++ program to print reverse of linked list
// without extra space and without modifications.
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Counts no. of nodes in linked list */
int getCount(struct Node* head)
{
int count = 0; // Initialize count
struct Node* current = head; // Initialize current
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}
/* Takes head pointer of the linked list and index
as arguments and return data at index*/
int getNth(struct Node* head, int n)
{
struct Node* curr = head;
for (int i=0; i<n-1 && curr != NULL; i++)
curr = curr->next;
return curr->data;
}
void printReverse(Node *head)
{
// Count nodes
int n = getCount(head);
for (int i=n; i>=1; i--)
printf("%d ", getNth(head, i));
}
/* Driver program to test count function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Use push() to construct below list
1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printReverse(head);
return 0;
}
Java
// Java program to print reverse of linked list
// without extra space and without modifications.
class GFG
{
/* Link list node */
static class Node
{
int data;
Node next;
};
static Node head;
/* Given a reference (pointer to pointer) to
the head of a list and an int, push a new node
on the front of the list. */
static void push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
head = head_ref;
}
/* Counts no. of nodes in linked list */
static int getCount(Node head)
{
int count = 0; // Initialize count
Node current = head; // Initialize current
while (current != null)
{
count++;
current = current.next;
}
return count;
}
/* Takes head pointer of the linked list and
index as arguments and return data at index*/
static int getNth(Node head, int n)
{
Node curr = head;
for (int i = 0; i < n - 1 && curr != null; i++)
curr = curr.next;
return curr.data;
}
static void printReverse()
{
// Count nodes
int n = getCount(head);
for (int i = n; i >= 1; i--)
System.out.printf("%d ", getNth(head, i));
}
// Driver Code
public static void main(String[] args)
{
/* Start with the empty list */
head = null;
/* Use push() to construct below list
1->2->3->4->5 */
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 2);
push(head, 1);
printReverse();
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to print reverse of linked list # without extra space and without modifications. ''' Link list node ''' class Node: def __init__(self, data): self.data = data self.next = None ''' Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. ''' def push( head_ref, new_data): new_node = Node(new_data) new_node.next = head_ref; head_ref = new_node; return head_ref ''' Counts no. of nodes in linked list ''' def getCount(head): count = 0; # Initialize count current = head; # Initialize current while (current != None): count += 1 current = current.next; return count; ''' Takes head pointer of the linked list and index as arguments and return data at index''' def getNth(head, n): curr = head; i = 0 while i < n - 1 and curr != None: curr = curr.next; i += 1 return curr.data; def printReverse(head): # Count nodes n = getCount(head); for i in range(n, 0, -1): print(getNth(head, i), end = ' '); # Driver code if __name__=='__main__': ''' Start with the empty list ''' head = None; ''' Use push() to construct below list 1.2.3.4.5 ''' head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); printReverse(head); # This code is contributed by rutvik_56
C#
// C# program to print reverse of
// linked list without extra space
// and without modifications.
using System;
class GFG
{
/* Link list node */
public class Node
{
public int data;
public Node next;
};
static Node head;
/* Given a reference (pointer to pointer)
to the head of a list and an int, push a
new node on the front of the list. */
static void push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
head = head_ref;
}
/* Counts no. of nodes in linked list */
static int getCount(Node head)
{
int count = 0; // Initialize count
Node current = head; // Initialize current
while (current != null)
{
count++;
current = current.next;
}
return count;
}
/* Takes head pointer of the linked list and
index as arguments and return data at index*/
static int getNth(Node head, int n)
{
Node curr = head;
for (int i = 0;
i < n - 1 && curr != null; i++)
curr = curr.next;
return curr.data;
}
static void printReverse()
{
// Count nodes
int n = getCount(head);
for (int i = n; i >= 1; i--)
Console.Write("{0} ", getNth(head, i));
}
// Driver Code
public static void Main(String[] args)
{
/* Start with the empty list */
head = null;
/* Use push() to construct below list
1->2->3->4->5 */
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 2);
push(head, 1);
printReverse();
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to implement above approach
// Link list node
class Node{
constructor(data){
this.data = data
this.next = null
}
}
// Given a reference (pointer to pointer) to the head
// of a list and an int, push a new node on the front
// of the list.
function push( head_ref, new_data){
let new_node = new Node(new_data)
new_node.next = head_ref;
head_ref = new_node;
return head_ref
}
// Counts no. of nodes in linked list
function getCount(head){
let count = 0; // Initialize count
let current = head; // Initialize current
while (current != null){
count += 1
current = current.next;
}
return count;
}
// Takes head pointer of the linked list and index
// as arguments and return data at index
function getNth(head, n){
let curr = head;
let i = 0
while(i < n - 1 && curr != null){
curr = curr.next;
i += 1
}
return curr.data;
}
function printReverse(head){
// Count nodes
let n = getCount(head);
for(let i=n;i>0;i--)
document.write(getNth(head, i),' ');
}
// Driver code
// Start with the empty list
let head = null;
// Use push() to construct below list
// 1.2.3.4.5
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
printReverse(head);
// This code is contributed by shinjanpatra
</script>
Producción:
5 4 3 2 1
Complejidad de tiempo : O (n) donde n es el número de Nodes en una lista enlazada dada
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shahnawaz_Ali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA