Reverse Traversing singly linked list in C++

22,128

Solution 1

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.

Solution 2

There's an old trick for traversing the list in reverse with a while loop.

You walk the loop in the forward direction, but as you leave each node, you reverse the link -- i.e., you get its current value (the pointer to the next node), but then set it so it contains a pointer to the previous node. When you reach the end of the list, you now have a singly-linked list that goes the opposite direction -- i.e., following the pointers will take you back to the beginning of the list.

So then you walk back to the beginning, printing each node's value out as you go, and (again) reversing the links so when you're done, the list is as it started, with links going from beginning to end.

Note, however, that this can lead to problems in (for one obvious example) multi-threaded code. The entire traversal of the list from beginning to end and back to the beginning has to be treated as a single, atomic operation -- if two threads try to traverse the list simultaneously, very bad things will happen. Likewise, making this exception-safe can be somewhat challenging as well.

IOW, these are rarely effective solutions to real problems (but the same is generally true of linked lists in general). They are, however, effective ways of showing an interviewer that you can play stupid linked-list tricks.

Solution 3

If your list is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:

1) You want to output the list reversed, your printList should look like this:

int printList(node* traverse)
{
    if (!traverse)
        return (-1);
    printList(traverse->next);
    std::cout << traverse->data << std::endl;
    return (0);
}

2) It is not really possible with a while loop, unless you do really ugly things like concatenating every node's data to the beginning of the result string that you will print.

3) Your main seems very strange to me. I don't understand why your 'head' variable is global, why not in the main itself?

Last but not least, why don't using std::list?

Solution 4

I was asked a question containing this in the interview. It was intended to traverse the single list from both ends simultaneously. So reversing the single list was not an option. Also, memory space complexity should be O(1). I try to solve with nested loops with O(n^2) time complexity. However, more effective way is to use XOR linked list which was mentioned by @chuckcottrill and @jerry-coffin. Single list can be converted to XOR linked list by applying xor operation to prev and next pointers of node. XOR linked list based on the following property of XOR operation.

a^a^b = b (order of left side is not important)

Let's consider a node in single list and its neighboring nodes:

  • X: address of prev node , Y: address of next node
  • While converting to XOR list Y' = X^Y (Y': new value of Y)
  • While reverse traversing on XOR list Y^(Y') =Y^Y^X=X

So we can attain prev node (X) and do reverse traversal. The following code converts the single list to XOR linked list and does reverse traversal (forward traversal is also possible at the same time):

    node* curr = head;
    node* prev = NULL;
    node* next= curr->next;

    while (curr) {
        next = curr->next;
        // apply xor to prev and next   
        curr->next = (node*)((uintptr_t)(prev)^(uintptr_t)(next));
        // move pointers forward
        prev = curr;
        curr = next;
    }
    // prev becomes tail node 
    
    // -- Reverse Traversal --
    curr = prev ; // curr points to tail 
    prev = NULL;
    node* temp;
    
    while (curr) {
        cout << curr->data << " ";
        temp = curr;
        // apply xor to prev and next  
        curr = (node*)((uintptr_t)(prev)^(uintptr_t)(curr->next));
        prev = temp;
    }
Share:
22,128
Sarp Kaya
Author by

Sarp Kaya

Updated on November 29, 2021

Comments

  • Sarp Kaya
    Sarp Kaya almost 2 years

    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?

  • Sarp Kaya
    Sarp Kaya over 10 years
    1 ) codepad.org/tqDgsXUk Segmentation fault 2) codepad.org/YiSfIMEz Not in a reverse order
  • Sarp Kaya
    Sarp Kaya over 10 years
    head is global because I thought for other functions it might require to be accessed globally. It's not a big issue. About std::list, because this is an interview question, they ask you to implement rather than using C++ STL
  • hanslovsky
    hanslovsky over 10 years
    1) take dreamstate's more detailed answer on that which is basically the same 2) true. With a while loop you will need a stack (last in first out) that you fill while going through the linked list. And then you have another loop while the stack is not empty and pop from the stack (what is what you basically do with the recursive calls).
  • lip
    lip over 10 years
    Well, then this is a C question. If I ever ask this question in an interview, I'm expecting the answer of the candidate to be "well, use standard containers", this is a sane reaction.
  • lip
    lip over 10 years
    @dreamstate it is possible in a while loop, provided you keep all node pointers in a stack-like container. And this is exactly what your recursive method do, in fact, piling the node pointers on the process stack... which has limited size, compared to the process heap.
  • roptch
    roptch over 10 years
    @lip yes that's what I said, you can do it with ugly things.. And yes using the heap may let you have more space (do we really need it?), but heap allocations, meaning a system call like sbrk(2) for each element will just multiply the execution time by 100 (I don't know, but a lot).
  • lip
    lip over 10 years
    @dreamstate you should try to profile it. I can't even get a 10% speed-up on the recursive version. Allocating space for pointers is not so costly.
  • ChuckCottrill
    ChuckCottrill about 10 years
    There is another trick, which uses XOR to store next and previous pointers in a single pointer (en.wikipedia.org/wiki/XOR_linked_list).
  • Jerry Coffin
    Jerry Coffin about 10 years
    @ChuckCottrill: I doubt it was original with me, but I wrote about that trick before Wikipedia existed. :-)
  • Jerry Coffin
    Jerry Coffin about 10 years
    @ChuckCottrill: As I said, I'm pretty sure it's not original with me (and as ugly as it is, I'd probably disclaim all knowledge of it if it really was mine).
  • ChuckCottrill
    ChuckCottrill about 10 years
    I was asked this on an interview once, my response was why would you want to do something so fragile?