Рубрики

Распечатать реверс связанного списка без реверсирования

Получив связанный список, выведите его в обратном порядке, используя рекурсивную функцию. Например, если заданный связанный список 1-> 2-> 3-> 4, тогда вывод должен быть 4-> 3-> 2-> 1.

Обратите внимание, что речь идет только о печати на обороте. Чтобы перевернуть сам список, посмотрите это

Уровень сложности:
Новичок

Алгоритм

printReverse(head)
  1. call print reverse for hed->next
  2. print head->data

Реализация:

C ++

// C ++ программа для печати реверса связанного списка
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел списка ссылок * /

class Node 

    public:

    int data; 

    Node* next; 

}; 

  
/ * Функция перевернуть связанный список * /

void printReverse(Node* head) 

    // Базовый вариант

    if (head == NULL) 

    return

  

    // выводим список после заголовка

    printReverse(head->next); 

  

    // После печати всего остального печатающая головка

    cout << head->data << " "

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Переместить узел в связанный список. Обратите внимание, что эта функция
меняет голову * /

void push(Node** head_ref, char new_data) 

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data; 

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref); 

  

    / * переместить голову в почар на новый узел * /

    (*head_ref) = new_node; 

  
/ * Сушильный код * /

int main() 

    // Давайте создадим связанный список 1-> 2-> 3-> 4

    Node* head = NULL; 

    push(&head, 4); 

    push(&head, 3); 

    push(&head, 2); 

    push(&head, 1); 

      

    printReverse(head); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C программа для печати реверса связанного списка
#include<stdio.h>
#include<stdlib.h>

   
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

   
/ * Функция перевернуть связанный список * /

void printReverse(struct Node* head)

{

    // Базовый вариант

    if (head == NULL)

       return;

  

    // выводим список после заголовка

    printReverse(head->next);

  

    // После печати всего остального печатающая головка

    printf("%d  ", head->data);

}

   
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Переместить узел в связанный список. Обратите внимание, что эта функция

  меняет голову * /

void push(struct Node** head_ref, char 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;

   
/ * Сушилка для проверки вышеуказанной функции * /

int main()

{

    // Давайте создадим связанный список 1-> 2-> 3-> 4

    struct Node* head = NULL;    

    push(&head, 4);

    push(&head, 3);

    push(&head, 2);

    push(&head, 1);

    

    printReverse(head);

    return 0;

}

Джава

// Java-программа для печати реверса связанного списка

class LinkedList

{

    Node head;  // заголовок списка

  

    / * Узел связанного списка * /

    class Node

    {

        int data;

        Node next;

        Node(int d) {data = d; next = null; }

    }

  

    / * Функция для печати реверса связанного списка * /

    void printReverse(Node head)

    {

        if (head == null) return;

  

        // распечатать список головного узла

        printReverse(head.next);

  

        // После того, как все остальное напечатано

        System.out.print(head.data+" ");

    }

  

    / * Служебные функции * /

  

    / * Вставляет новый узел в начало списка. * /

    public void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    / * Функция сушилки для проверки вышеуказанных методов * /

    public static void main(String args[])

    {

        // Давайте создадим связанный список 1-> 2-> 3-> 4

        LinkedList llist = new LinkedList();

        llist.push(4);

        llist.push(3);

        llist.push(2);

        llist.push(1);

  

        llist.printReverse(llist.head);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

C #

// C # программа для печати реверса связанного списка

using System;

  

public class LinkedList

{

    Node head; // заголовок списка

  

    / * Узел связанного списка * /

    class Node

    {

        public int data;

        public Node next;

        public Node(int d) 

        {

            data = d; next = null;

        }

    }

  

    / * Функция для печати реверса связанного списка * /

    void printReverse(Node head)

    {

        if (head == null) return;

  

        // распечатать список головного узла

        printReverse(head.next);

  

        // После того, как все остальное напечатано

        Console.Write(head.data + " ");

    }

  

    / * Служебные функции * /

  

    / * Вставляет новый узел в начало списка. * /

    public void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    / * Функция драйвера для проверки вышеуказанных методов * /

    public static void Main(String []args)

    {

        // Давайте создадим связанный список 1-> 2-> 3-> 4

        LinkedList llist = new LinkedList();

        llist.push(4);

        llist.push(3);

        llist.push(2);

        llist.push(1);

  

        llist.printReverse(llist.head);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

4 3 2 1

Сложность времени: O (n)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Распечатать реверс связанного списка без реверсирования

0.00 (0%) 0 votes