CODEWITHSUNDEEP
c++reverse
Brian Brown
Brian Brown

Reputation: 4311

Reverse print linked list in C++

I would like to implement linked list. I wrote an insert list method, print method but have problems with reverse printing. The main problem is the reverse printing prints a normal list, not reversed:

#include <iostream>

struct Node
{
    int value;
    struct Node *next;
};

struct List
{
    struct Node *first, *last;
};

Node* node(int v)
{
    Node *newNode = new Node();
    newNode->value = v;
    newNode->next = NULL;
    return newNode;
}

List*  list()
{
    List *newList = new List();
    newList->first = NULL;
    newList->last = NULL;
    return newList;
}

List*  insert(List* s, Node* n)
{
    if (s->last == NULL)
    {
        n->next = s->last;
        s->last = n;
        s->first = n;
        return s;
    }

    s->last->next = n;
    s->last = s->last->next;
    return s;
}

void  print(List* s)
{
    Node *tmp = s->first;
    while(tmp)
    {
        std::cout << tmp->value << ' ';
        tmp = tmp->next;
    }
    std::cout << '\n';
}

void reverse_print(List* s)
{
    if(s->first == NULL)
    {
        std::cout << '\n';
        return;
    }

    else
    {
        std::cout << s->first->value << ' ';
        s->first = s->first->next;
        reverse_print(s);
    }
}

int main(int argc, char *argv[])
{
    List *myList2;
    myList2 = list();

    myList2 = insert(myList2, node(3));
    myList2 = insert(myList2, node(5));
    myList2 = insert(myList2, node(7));
    myList2 = insert(myList2, node(9));
    myList2 = insert(myList2, node(5));
    myList2 = insert(myList2, node(34));
    myList2 = insert(myList2, node(67));

    print(myList2);

    reverse_print(myList2);
}

Upvotes: 0

Views: 888

Answers (2)

molbdnilo
molbdnilo

Reputation: 66371

  1. You shouldn't modify the list that you're printing.
  2. You should recursively print "the rest of the list" first.

The best way is to have a separate function for printing nodes:

void reverse_print(Node* n)
{
    if (n != NULL)
    {
        reverse_print(n->next);
        std::cout << n->value << ' ';
    }
}

void reverse_print(List* s)
{
    reverse_print(s->first);
}

Upvotes: 4

Naman
Naman

Reputation: 31868

Change

else
    {
        std::cout << s->first->value << ' ';
        s->first = s->first->next;
        reverse_print(s);
    }

to 

else
    {
        reverse_print(s);
        s->first = s->first->next;
        std::cout << s->first->value << ' ';   
    }

should help you use the recursion effectively.

Upvotes: 2

Related Questions