3
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ the problem doesnt mention an upper limit on the list size, so this solution is invalid. \$\endgroup\$ – pm100 Jul 27 '16 at 1:01
  • 1
    \$\begingroup\$ It's possible to do this with O(1) memory requirements by reversing the linked list in place, printing it, then reversing it again. The best solution depends on how you're trying to optimize the code. \$\endgroup\$ – Score_Under Jul 27 '16 at 1:46
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Since this is Code Review, you should also mention why you think this is a better solution. \$\endgroup\$ – 200_success Jul 27 '16 at 0:05
  • \$\begingroup\$ problem here is the the problem doesnt state an upper bound for the list size, recursion is gonna fail if you have thousands of objects. (Unless you have an awesome compiler that can optimize to tail recursion to chaining) \$\endgroup\$ – pm100 Jul 27 '16 at 1:01
  • \$\begingroup\$ @pm100 I doubt that any compiler would do that, since this function is not tail-recursive. \$\endgroup\$ – 200_success Jul 27 '16 at 1:24
  • \$\begingroup\$ I think this is a better solution because it is cleaner, but it is also recursive so as @pm100 mentioned, it will fail with thousands of objects because it will use up too much memory in the stack \$\endgroup\$ – Clefairy Jul 27 '16 at 3:49
0
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.