reverse a single linked list

[sam_cit]

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]

sa*****@yahoo.co.in 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]

>
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]

sa*****@yahoo.co.in 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]

sa*****@yahoo.co.in 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
a linked list?

Hint #2: Do you know how to add an item at the beginning
of a linked list?

--
Eric Sosman
es*****@acm-dot-org.invalid

[sam_cit]

>
Hint #2: Do you know how to add an item at the beginning
of a linked list?

--

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]

sa*****@yahoo.co.in wrote:

> Hint #2: Do you know how to add an item at the beginning
of a linked list?

--

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
es*****@acm-dot-org.invalid

[sam_cit]

>

>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;

while(original_head != NULL)
{
original_head_next = original_head->ptr;
origianl_head->ptr = new_head;
new_head = original_head;
original_head = original_head_next;
}

return(new_head);

}

Did you mean any other solution???

[pete]

Ico wrote:

>
sa*****@yahoo.co.in 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]

sa*****@yahoo.co.in 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;

while(original_head != NULL)
{
original_head_next = original_head->ptr;
origianl_head->ptr = new_head;
new_head = original_head;
original_head = original_head_next;
}

return(new_head);

}

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
es*****@acm-dot-org.invalid

[CBFalconer]

sa*****@yahoo.co.in wrote:

>
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?

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

which requires that a 'nodeptr' be defined to point to a struct
with at least a next field, of type nodeptr. Usage is of the form:

nodeptr root;
....
/* code to form the list */
...
root = revlist(root)

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

[Randy Howard]

Ico wrote
(in article
<45***********************@dreader29.news.xs4all.n l>):

sa*****@yahoo.co.in 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.

Wasting space on unneeded links is also frowned upon in the
embedded space.

--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw