Part 1 of 26 in Linked List - set 02  

Print elements of a linked list in reverse order by animeshn

Problem statement

Given a singly linked list of integers, print the elements of linked list in reverse order.

Input

You need to write a function with signature "void ReversePrint(Node *head)" that will take address of the head node as argument.

Output

Your function must print elements in the list in reverse order. Each element in the list should be printed on a separate line.

To print the elements in reverse order, we can use recursion.

For those who are new to this term, recursion is simply a function calling itself.

To learn recursion basics, I suggest watching this video.

For the problem, lets try printing the numbers in the same order as in the list recursive fashion.

Recursion comprises a stack of function calls, having the LIFO (Last In First Out) structure.

Once the function at the top of the stack terminates, it is popped out, and control is passed to the next function in the call stack.

/* To print elements of in the same order as in the list */
void print(Node *head)
{
	/* base case which is important for every recursion */
	if (head == NULL) {
		/* we reach the end of the list */
		return;
	}
	
	/* print the element in the node */
	cout << head->data << endl;
	
	/* recursive call to for printing the next node */
	print(head->next);
	
	return;
}

Iteration for printing the next element of the list is done in a recursive manner. Elements are printed in the same order as stored in the list.

Once the base case is encountered, it implies no more recursive calls are allowed, or we have reached the end of the list.

For printing the elements in reverse order, we can have the same function, except that the order of statements is changed.

For the earlier case, we printed the element, and called for recursion to the next node. Here, we first make call to the recursion for the next node, and then print the value.

The following function prints elements in reverse order.


/* To print elements of list in the reverse order */
void print_reverse(Node *head)
{
	/* base case which is important for every recursion */
	if (head == NULL) {
		/* we reach the end of the list */
		return;
	}
	
	/* recursive call to print the next node in the list */
	print_reverse(head->next);
	
	/* print the element in the node */
	cout << head->data << endl;
	
	return;
}

Still not clear, Watch this video, and have a better idea of what's going on.

editorial written by shivshnkr

/* function to print elements of list in the reverse order */
void ReversePrint(Node *head)
{
	/* base case which is important for every recursion */
	if (head == NULL) {
		/* we reach the end of the list */
		return;
	}
	
	/* recursive call to for printing the next node in the list */
	ReversePrint(head->next);
	
	/* print the element in the node */
	cout << head->data << endl;
	
	return;
}

featured solution by shivshnkr



To try out your code



Sign in

Sign up