Traverse from end to front ( C++ LL Q:1 )

Question

Hi,

---

int LinkedList::DoStuff()
{
Node *Current    = next_;
while ( Current != NULL )
    {
     Current = Current->next_;
     length_++;
    }
    // At the last iteration we have reached the end/tail/last node
    return length_;
}

---

there are no more nodes beyond the last. How can i traverse to the tail-end to the front-head?

Answer 1

Is your linked list class doubly-linked or singly-linked? If there is no previous pointer inside each node, you can't traverse backwards.

I also suggest you post more code and take the time to make your question readable.

In addition, if this is a homework question, you need to use the homework tag.

Answer 2

Unless your linked list is a doubly-linked one, this is difficult to do. Recursion is one way, assuming you don't have lists so big that you'll run out of stack space, something like this (pseudo-code):

DoStuffBackwards (currNode) {
    if (currNode != NULL) {
        DoStuffBackwards (currNode->next);
        // Process currNode here.
    }
}

DoStuffBackwards (firstNode);

This works because you keep calling DoStuffBackwards() for the next node until you exhaust the list then, as you roll back up the recursion stack, you process each node.

Answer 3

If you just want to go backwards from last node to current node, than Pax's answer (using recursion) is your best bet, also see my version below. If your current node is not the head of your non-circular-singly-linked-list, and you want to go from current node to head node, it is impossible.

int LinkedList::DoStuff()
{
    return DoStuffBackward(next_, 0);
}

int LinkedList::DoStuffBackward(Node* node, int n)
{
    if (!node)
    {
        return n;
    }

    int len = DoStuffBackward(node->next_, n + 1);
    std::cout << "doing stuff for node " << n << std::endl;
    return len;
}

Answer 4

This has the smell of homework, so no code, but here's an overview of a solution that doesn't require recursion:

If you want to run through the list backward one option to relink the list to point backwards as you're traversing it to find the end. Then as you re-traverse the list (which visits the nodes in the reverse order from the original list) you repeat the relinking same as before and the list ends up in its original order.

This is simple in concept, but handling the pointers and links correctly (especially at the start and end of the list) can be a bit tricky.

Answer 5

Recursion can work, as can building an auxiliary data structure, such as an array with one entry for each element of the original list. If you want a solution for a single-threaded list without requiring O(n) extra storage, the best bet is to reverse the list in place as Michael suggests. I wrote an example for this, [but I'll leave it out given the concern about homework]. One caution about reversing the list: if there are any other data structures that hold pointers to the original list, and you might be accessing them during your traversal, they won't work if they need to access the list while it's reversed, and this might lead to data corruption if they try to modify the list.

Update: Ok, here's the (C++) routine to reverse a list in place. It hasn't been tested, though. And I'll note that if this is homework, the poster still needs to figure out how to use this routine correctly to get a complete answer.

Node *ReverseList(Node *head) {
    // Reverse a single-threaded list in place, return new head
    Node *prev=NULL;
    Node *cur=head;

    while (Node *next=cur->next_) {
     cur->next_ = prev;
     prev = cur;
     cur = next;
    }
    cur->next_ = prev;
    return cur;
}

Answer 6

push the list on a stack and then pop them off.