Reverse the order of a Singly Linked List

given the following types and variables have been defined and are available for use:

struct nodetype
{
char *Airport;
struct nodetype *Link;
};

typedef nodetype NodeType;

And given that L =={DUS, ORD, DAN} before hand.

I'm trying to write a function Reverse(&L) that reverses the order of the list. I've copied the specification for the problem into the comments just before the function.

What I have thus far does remove a node, but when I start building the new node, I get lost. I can't declare any more variables than are listed in the function spec though it seems to me that I need one more temp variable to pull this off.


/*Write a function, Reverse(&L), which reverses the order of the nodes
on list L. Must write two subroutines to remove the first node N of a
list L1 and to insert a node N as the new first node on a list L2. Then,
starting with an empty list L2=NULL, successively remove nodes from L1
and insert them on L2 until L1 is empty.*/

void ReverseList(NodeType **L)
{
NodeType *M, //temp node
*N; //new list

N=NULL;
*L=(*L)->Link; //move in from the head node.
while(*L!=NULL){
//remove the first node from L.
M=*L; //M equals first node
//N=(*L)->Link; // N equals second node.
*L=(*L)->Link; //remove first node.

//add the removed first node to the head of node.
if(N==NULL){N=(NodeType*)malloc(sizeof(NodeType)); }
N->Link=M; //add node to head

}
}

You can wright it recursivly.

For your base case you have a single list and a empty list.
You know that the reversal of a single list is the same single list and the reversal of an empty list an empty list.

If the list has more than one element such as
(a b c d e f g) the reversal is
(reversal(b c d e f g) a) = (g f e d c b a)) This all should be really simple to code in c.

Another way is to use a stack so you have
(a b c d e f g) You push them one by one onto the stack, destroy
the old list and if your stack is a linked list your done.

You can do it recursivly.

For your base case you have a single list and a empty list.
You know that the reversal of a single list is the same single list and the reversal of an empty list an empty list.

If the list has more than one element such as
(a b c d e f g) the reversal is
(reversal(b c d e f g) a) = (g f e d c b a)) This all should be really simple to code in c.

Another way is to use a stack so you have
(a b c d e f g) You push them one by one onto the stack, destroy
the old list and if your stack is a linked list your done.

There's some materials here if you're interested.

Thanks everyone who's posted. Hammer, that's a cool document.
now, the issue here is that I can't do this as a recursive call. We are not even studying recurive calls yet. I conceed that recursion is a neat and efficient way of reordering the list, but can't do it yet. so, bear with me.
I have to write two sub-routines and pass the pointers around inside them.

so for instance, NodeType * RemoveNode(*L or &L ??? ) //not sure how to pass this parameter from within a function that's already double dereferencing. So the *L might be incorrect.

Then another sub routine.
void addRemovedNode(*L or &L??)

anyone willing to take a stab at this? I've been trying for days. Please read my original post before spending any time with this.

Mike

For parameters all you need too pass a pointer
to a pointer because you want to remove the head of the list or
if you are doing c++ you can do a reference to a pointer.

I don't want to solve your homework problem because
otherwise you won't get anywhere. I'm guessing what your doing is removing nodes from the front of the list and inserting them into the back of a second list. Anyways the best
way to do this is create a diagrams like they show you in the
pdf file. For addRemovedNode what you do is pass in the pointer to the pointer of the head of the list. If the list is empty
then assign the head of the list to the new node. Else you traverse the list by following the next pointers but you also keep track of previous node. Then you assign prev->link to the new node. This is simple but slow.

Quote:

---

Originally posted by Nick
For parameters all you need too pass a pointer
to a pointer because you want to remove the head of the list or
if you are doing c++ you can do a reference to a pointer.

I don't want to solve your homework problem because
otherwise you won't get anywhere. I'm guessing what your doing is removing nodes from the front of the list and inserting them into the back of a second list. Anyways the best
way to do this is create a diagrams like they show you in the
pdf file. For addRemovedNode what you do is pass in the pointer to the pointer of the head of the list. If the list is empty
then assign the head of the list to the new node. Else you traverse the list by following the next pointers but you also keep track of previous node. Then you assign prev->link to the new node. This is simple but slow.

---

Hi Nick, et al.
Thanks for your reply. I did solve my problem with reversing the list. Thanks goes to everyone that replied. I think I am getting a good picture of how to pass pointers around. I do have another question regarding passing a pointer to a pointer (or &Lin the case of my example). I always build a list with a head(dummy) node. So the first node's data is always empty. If I do that, then do I always need to pass the structure by using &L?

Inotherwords, in the case where the linked list has a head node I don't need to use the & operator. right?

Thanks
Mike

as long as your head node isn't dynamically allocated, then you wouldn't *need* to pass a pointer to a function, you *could* pass the structure, but it is faster to pass a pointer than to pass and entire structure because the pointer is smaller than the structure. It's not like it adds a lot of complexity to use the pointer (you can actually just pass &nameofyourstruct) All that you have to do different in the function is use a -> to access the data in the struct instead of a . It's that easy, and it's faster.