Imprima el reverso de una lista enlazada sin espacio adicional ni modificaciones

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *