Thread: Reverse the order of a Singly Linked List

  1. #1
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72

    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

    }
    }
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  2. #2
    Nick
    Guest
    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.

  3. #3
    Nick
    Guest
    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.

  4. #4
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    There's some materials here if you're interested.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  5. #5
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72
    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
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  6. #6
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  7. #7
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72
    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
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  8. #8
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    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.
    Away.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. reversing a singly linked list
    By galmca in forum C Programming
    Replies: 6
    Last Post: 02-07-2005, 10:25 AM