Reversing a linked list iteratively

[Paul]

I'm confused by the code below for reversing a linked list although it seems to work. What puzzles me is that changes to p affect rest. I don't know why this is so, because rest is a copy. For example, why does p->next->next = p; change rest? rest is an earlier copy of p->next. rest is not a reference.

Thanks a lot for explaining it,

Paul

template<typename T>
void reverseRecursive(node<T>*& p) {

if (!p) return;
node<T>* rest = p->next;

if (!rest) return;
reverseRecursive(rest);

p->next->next = p;
p->next = nullptr;
p = rest;
}

[David Bradshaw]

Paul,

You need to understand that rest is a pointer, defined by the following line:

> node<T>* rest = p->next;

After this line of code, rest is pointing to the same piece of data that
p->next points to. In other words, you are not copying any data, but
creating pointers or 'bookmarks' into the existing data structure.

This is a reverse-in-place algorithm, which means you are not creating a
copy of your data structure at all, just manipulating the pointers to
achieve a reversal of its elements.

David

--

[Christopher Pisz]

Draw it out on paper:

...P..R...// Second level recursion
P..R......// First level recursion
[1][2][3].// memory

I am not clear on what change to p is puzzling you or what copy you are
referring to. Nothing is copied anywhere, but pointers are set to point
to locations other pointers are pointing to. If by copy, you mean the
location the pointer is pointing to at that level in the recursive
stack, it doesn't change, but the contents of the location do.






--
I have chosen to troll filter/ignore all subthreads containing the
words: "Rick C. Hodgins", "Flibble", and "Islam"
So, I won't be able to see or respond to any such messages
---

[Mr Flibble]

Using recursion to do this is a BAD idea as it doesn't SCALE. Consider a
container with 10000000 elements...

/Flibble

[Paul]

On Monday, July 27, 2015 at 5:15:23 PM UTC+1, Christopher Pisz wrote:
> On 7/27/2015 10:29 AM, Paul wrote:
> > I'm confused by the code below for reversing a linked list although it seems to work. What puzzles me is that changes to p affect rest. I don't know why this is so, because rest is a copy. For example, why does p->next->next = p; change rest? rest is an earlier copy of p->next. rest is not a reference.
> >
> > Thanks a lot for explaining it,
> >
> > Paul
> >
> > template<typename T>
> > void reverseRecursive(node<T>*& p) {
> >
> > if (!p) return;
> > node<T>* rest = p->next;
> >
> > if (!rest) return;
> > reverseRecursive(rest);
> >
> > p->next->next = p;
> > p->next = nullptr;
> > p = rest;
> > }
> >
>
>
> Draw it out on paper:
>
> ...P..R...// Second level recursion
> P..R......// First level recursion
> [1][2][3].// memory
>
> I am not clear on what change to p is puzzling you or what copy you are
> referring to. Nothing is copied anywhere, but pointers are set to point
> to locations other pointers are pointing to. If by copy, you mean the
> location the pointer is pointing to at that level in the recursive
> stack, it doesn't change, but the contents of the location do.

to see or respond to any such messages
> ---

I get it now. Thanks a lot to both of you.

Paul