10041. LinkedList Print in reverse order

Given a linked list. Print its elements in reverse order.

Definition of a single linked list:

//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) {}

};

Implement function PrintReverse that prints the elements of linked list in the reverse order.

// Java

int PrintReverse (ListNode head)

// C++

int PrintReverse(ListNode *head)

Example

Function PrintReverse prints in one line the elements of a linked list in the reverse order: 3 2 1.

SOLUTION

linked list

Algorithm analysis

Implement the PrintReverse function as follows: first, print the elements of the tail of the linked list in reverse order, and then print the value of the head.

PrintReverse(ListNode head)

if head == NULL, return NULL;

PrintReverse(head->next) ;

print head->val;

Example

Consider how to print the list given in example in the reverse order.

Algorithm realization

First, print recursively the elements of the tail of the linked list in reverse order, and then print the value of the head.

void PrintReverse(ListNode *head)

{

if (head == NULL) return;

PrintReverse(head->next);

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

}

Java realization

void PrintReverse(ListNode head)

{

if (head == null) return;

PrintReverse(head.next);

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

}