Print element in a linked list in reverse

Question

I solved this problem in C++ and was looking for feedback on my code. I'm not sure if storing the data in an array and looping through it in reverse and printing was the right approach since this challenge was to use linked lists, but I didn't know how else to do it:

You are given the pointer to the head node of a linked list and you need to print all its elements in reverse order from tail to head, one element per line. The head pointer may be null meaning that the list is empty - in that case, do not print anything!

/* Print elements of a linked list in reverse order as standard output head pointer could be NULL as well for empty list Node is defined as struct Node { int data; struct Node *next; } */ void ReversePrint(Node *head) { // creates nodes named current, prev, next struct Node *current, *prev, *next; // sets current and previous to their respective values. current is head because it is starting position while previous is where we want the head to be pointing, which is null, since we are reverse a linked list current = head; prev = NULL; // allocate memory to an array and initialize i=0 int array[100], i=0; while (current != NULL) { // store data into an array to print out later array[i] = current->data; i+=1; // updates next [current, link] -> [int, link] = next next = current->next; // updates link of current.next to value of previous current->next = prev; // updates previous value prev = current; // updates current value current = next; } // at the end of list, sets head to the last value in linked list which is previous head = prev; // goes through array in reverse order and prints for(int j=i-1; j>=0; j--) { cout<<array[j]<<endl; } } 

Answer 1

This approach is fine if you know the linked list will always be less than 100 elements. To fix this issue while still using the same method, you could iterate through the linked list first to count the number of elements needed in your array.

If I were doing this problem, I'd look at using a stack... just push all the elements onto the stack, then pop them all off again to print them. This way we avoid iterating through the linked list twice (once to count, once to store in an array), while still solving to problem.

Answer 2

I figured it out using a recursive function. What it does is it loops through the linked list until the end, creating a recursion tree, then executes the print in reverse, when going down the recursion tree.

 void ReversePrint(Node *head) { if (head == NULL) { return; } // recursion tree. loops through until end of linked list ReversePrint(head->next); // once the recursive is done, then prints head->data going back down the recursion tree. printf("%d\n", head->data); } 

Answer 3

In terms of making things cleaner, @Clefairy code does justice. Few things I could point out here is

• You want to make your ReversePrint more generic, so it wise to use STL Containers i.e vector<int> . Using an Array, the size has to be fixed and can not be dynamic.

• You need all these variables *current, *prev, *next as you don't have to track the nodes. All you need to do is keep changing head to head->next till head is null, just like I have done below.

  void ReversePrint( Node *head ) { std::vector<int> nodeList; if ( head != NULL ) { while ( head != NULL ) { nodeList.push_back( head->data ); head = head->next; } for ( std::vector<int>::iterator it = nodeList.end() - 1; it != nodeList.begin() - 1; --it ) { std::cout << *it << endl; } } } 

• To print from the last item, vector provides functions like begin , end that allows you change the location of the iterator as shown above

• Just to make your code look neater, separate each variable declaration e.g struct Node *current, *prev, *next

to

struct Node *current, *prev, *next;