Reverse Traversing singly linked list in C++

c++, linked-list, singly-linked-list, traversal

Solution

They are four possible ways to achieve this, each of which having its own merits.

Recursion

void print_list(node* traverse)
{
    if (traverse == NULL) return;
    print_list(traverse->next);
    std::cout << traverse->data << std::endl;
}

This is maybe the first answer to come in mind. However, the process stack size is limited, so recursion has a pretty low limit. A big list will provoke a stack overflow. This is not a very good design in C++.

Iteration

void print_list(node *n)
{
    using namespace std;
    deque<node*> res;
    for(;n != NULL; n = n->next) res.push_back(n);
    for_each(res.rbegin(), res.rend(), [](node* n){cout << n->data << endl;});
}

Of course, if you want to make it the iterative way, you will need to stack the node pointers yourself (on the process heap) and not delegate this job to the call stack. This method lets you print far bigger lists, and is O(n) in computations. It is, however O(n) in memory usage, but you already have a list which use O(n) memory. So this should not be an issue. However, you may really need to avoid memory consumption. Which brings us to the next idea.

Double iteration

void print_list(node *head)
{
    node* last = NULL;
    while(last != head)
    {
        node* current = head;
        while(current->next != last)
            current = current->next;
        std::cout << current->data << std::endl;
        last = current;
    }
}

This may seem a dumb solution, as it has O(n^2) complexity, but that is computation-complexity. It has O(1) memory complexity and, depending on the actual context and exact problem, it may be the answer you need. But this O(n^2) complexity is a lot to pay. Especially if n is so big you wanted to avoid another O(n) allocation. Which brings us to the last idea.

Hack the container

void print_list(node *head)
{
    node* last = NULL;
    for(node* next; head != NULL; head = next)
    {
        next = head->next;
        head->next = last;
        last = head;
    }
    for(node* next; last != NULL; last = next)
    {
        next = last->next;
        last->next = head;
        head = last;
        cout << last->data << endl;
    }
}

You first modify the container, then iterate in your new order. On a single-linked list, you can just reverse the links, then reverse-iterate while reversing the links again. The beauty of it is it stays O(n) in computing, and O(1) in memory. The problem is that you invalidate the full container while doing this : your outputing operation does not leave the list constant : this is not exception-safe: if your operation fails in middle of iteration, the list is not valid anymore. This may or may not be an issue depending on the problem.

Problem

Recently I have been asked this question on an interview. All I could do is traverse from 9 to 1 from a linked list starting from 0 to 9. Here is the code: ``` #include <iostream> typedef struct node { int data; // will store information node *next; // the reference to the next node }; node *head; int printList(node *traverse) { if (traverse->next == NULL) { return -1; } traverse=traverse->next; printList(traverse); cout << traverse->data << endl; return 0; } int main() { node *temp = NULL; node *begin = NULL; for (int i = 0; i < 10; i++) { temp = new node; temp->data = i; if (begin == NULL) { begin = temp; } if (head != NULL) { head->next = temp; } head = temp; head->next = NULL; } head = begin; printList(head); return 0; } ``` 1) How can I print 0(the first element) with the `printList()` recursive function? 2) How can I replace `printList()` recursive function with while loop? 3) If asked in an interview, does the `main()` function has proper node initialisation and insertation?

Original source