10041. LinkedList Вывод в обратном порядке

Задан связный список.  Выведите его элементы в обратном порядке.

Определение связного списка:

//Java

class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}

// C++

class ListNode

{

public:

int val;

ListNode *next;

ListNode(int x) : val(x), next(NULL) {}

};

Реализуйте функцию PrintReverse, которая выводит элементы связного списка в обратном порядке.

// Java

int PrintReverse (ListNode head)

// C++

int PrintReverse(ListNode *head)

Пример

Функция PrintReverse выведет в одной строке элементы списка в обратном порядке: 3 2 1.

РЕШЕНИЕ

связный список

Анализ алгоритма

Реализуем функцию PrintReverse следующим образом: сначала выведем в обратном порядке элементы хвоста списка, после чего выведем значение головы.

PrintReverse(ListNode head)

если head == NULL, то вернуть NULL;

PrintReverse(head->next) ;

Вывести head->val;

Пример

Рассмотрим вывод списка, приведенного в примере, в обратном порядке.

Реализация алгоритма

Сначала рекурсивно выводим в обратном порядке элементы хвоста списка, после чего выводим значение головы.

void PrintReverse(ListNode *head)

{

if (head == NULL) return;

PrintReverse(head->next);

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

}

Java реализация

void PrintReverse(ListNode head)

{

if (head == null) return;

PrintReverse(head.next);

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

}