Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > reverse a single linked list

Reply
Thread Tools

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?

 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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.

 
Reply With Quote
 
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
 
Reply With Quote
 
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
a linked list?

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

--
Eric Sosman
(E-Mail Removed)lid
 
Reply With Quote
 
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
> 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?

 
Reply With Quote
 
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
>> 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
(E-Mail Removed)lid

 
Reply With Quote
 
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)
{
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???

 
Reply With Quote
 
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
 
Reply With Quote
 
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;
>
> 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
(E-Mail Removed)lid
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reverse search in a singly-linked list RAJASEKHAR KONDABALA C Programming 20 02-27-2011 12:53 PM
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
What's wrong in my function of reverse the doubly linked list with dummy node. Daniel C Programming 5 10-27-2004 10:16 PM
Reverse a linked list Perpetual Snow C Programming 9 11-27-2003 01:58 AM



Advertisments