Velocity Reviews > reverse a single linked list

# reverse a single linked list

sam_cit@yahoo.co.in
Guest
Posts: n/a

 12-17-2006
Hi Everyone,

I want to actually reverse a single linked list without using many
variables, i have a recurssive solution, but i wanted an iterative one.
can anyone help me on this?

Ico
Guest
Posts: n/a

 12-17-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> Hi Everyone,
>
> I want to actually reverse a single linked list without using many
> variables, i have a recurssive solution, but i wanted an iterative one.

Why would you want that, is your recursive solution not good enough ?

--
:wq
^X^Cy^K^X^C^C^C^C

sam_cit@yahoo.co.in
Guest
Posts: n/a

 12-17-2006

>
> Why would you want that, is your recursive solution not good enough ?
>

Yes, recursive solution is good but uses a lot of stack space and it
might not be helpful in a envirnoment where stack space is limited like
embedded systems where recursive functions are normally not encouraged.

Ico
Guest
Posts: n/a

 12-17-2006
(E-Mail Removed) wrote:
>
>>
>> Why would you want that, is your recursive solution not good enough ?
>>

>
> Yes, recursive solution is good but uses a lot of stack space and it
> might not be helpful in a envirnoment where stack space is limited like
> embedded systems where recursive functions are normally not encouraged.

Use a doubly linked list then.

-
:wq
^X^Cy^K^X^C^C^C^C

Eric Sosman
Guest
Posts: n/a

 12-17-2006
(E-Mail Removed) wrote:
> Hi Everyone,
>
> I want to actually reverse a single linked list without using many
> variables, i have a recurssive solution, but i wanted an iterative one.
> can anyone help me on this?

Since this has the odor of homework about it, I'll just
offer a few hints:

Hint #1: Do you know how to remove the first item from

Hint #2: Do you know how to add an item at the beginning

--
Eric Sosman
(E-Mail Removed)lid

sam_cit@yahoo.co.in
Guest
Posts: n/a

 12-17-2006

>
> Hint #2: Do you know how to add an item at the beginning
>
> --

Thanks very much for the hints, did you mean to say add an item at the
end of the list?

>From your hints, i think of a solution where in the last_node->ptr is

made to point to first node and this logic needs to be excecuted as
many times as many as strlen(string). Is this the solution you meant or
any other improvements are possible?

Eric Sosman
Guest
Posts: n/a

 12-17-2006
(E-Mail Removed) wrote:
>> Hint #2: Do you know how to add an item at the beginning
>>
>> --

>
> Thanks very much for the hints, did you mean to say add an item at the
> end of the list?

Hint #3: No.

>>From your hints, i think of a solution where in the last_node->ptr is

> made to point to first node and this logic needs to be excecuted as
> many times as many as strlen(string). Is this the solution you meant or
> any other improvements are possible?

No, and yes.

You are working too hard: There exists a much simpler
solution than those you seem to be thinking about.

--
Eric Sosman
(E-Mail Removed)lid

sam_cit@yahoo.co.in
Guest
Posts: n/a

 12-17-2006
>
> >>From your hints, i think of a solution where in the last_node->ptr is

> > made to point to first node and this logic needs to be excecuted as
> > many times as many as strlen(string). Is this the solution you meant or
> > any other improvements are possible?

>
> No, and yes.
>
> You are working too hard: There exists a much simpler
> solution than those you seem to be thinking about.
>

Yeah, i think so, i just got a solution but i don't think it utilises
your hints, it goes like this

reverse(stuct list* node)
{

{
}

}

Did you mean any other solution???

pete
Guest
Posts: n/a

 12-17-2006
Ico wrote:
>
> (E-Mail Removed) wrote:
> >
> >>
> >> Why would you want that,
> >> is your recursive solution not good enough ?
> >>

> >
> > Yes, recursive solution is good but uses a lot of stack space and it
> > might not be helpful in a envirnoment
> > where stack space is limited like
> > embedded systems where recursive
> > functions are normally not encouraged.

>
> Use a doubly linked list then.

A doubly linked list has nothing to do with OP's stated problem.

--
pete

Eric Sosman
Guest
Posts: n/a

 12-17-2006
(E-Mail Removed) wrote:
>>> >From your hints, i think of a solution where in the last_node->ptr is
>>> made to point to first node and this logic needs to be excecuted as
>>> many times as many as strlen(string). Is this the solution you meant or
>>> any other improvements are possible?

>> No, and yes.
>>
>> You are working too hard: There exists a much simpler
>> solution than those you seem to be thinking about.
>>

>
> Yeah, i think so, i just got a solution but i don't think it utilises
> your hints, it goes like this
>
> reverse(stuct list* node)
> {
> struct list* original_head = node;
> struct list* new_head = NULL;
> struct list* original_head_next = NULL;
>
> {
> }
>
>
> }
>
> Did you mean any other solution???

That's the one I meant, although I would have written it
with fewer auxiliary variables. One way to look at this
approach is to think of it as removing the first node from
the old list (hint #1) and pushing it onto the start of the
new list (hint #2), and repeating until the old list is empty.

Start:
old -> A -> B -> C ->|
new ->|

Step 1:
old -> B -> C ->|
new -> A ->|

Step 2:
old -> C ->|
new -> B -> A ->|

Step 3:
old ->|
new -> C -> B -> A ->|

Or, to relate it to another common experience: Hold a
deck of playing cards face down, and deal the cards one at
a time (still face down) onto a pile on the table in front
of you. How does the order of the cards in the dealt pile
relate to the order in the original deck?

--
Eric Sosman
(E-Mail Removed)lid