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]

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 ?

 

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

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]

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?

 

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

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

Hint #3: No.

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.

 

[sam_cit]

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]

Use a doubly linked list then.

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

 

[Eric Sosman]

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?

 

[CBFalconer]

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)

 

[Randy Howard]

Ico wrote
(in article

Use a doubly linked list then.

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