Thread: reverse a singly linked list

  1. #1
    Registered User ivandn's Avatar
    Join Date
    Oct 2001
    Posts
    49

    reverse a singly linked list

    Can anyone reverse a singly linked list in a graceful manner?

    Thank you for your help.
    Ivan

  2. #2
    Registered User ivandn's Avatar
    Join Date
    Oct 2001
    Posts
    49
    I dont like the way the attachment worked out. Here is the framework. Thanks again anyone who can give this a try. I have been banging my head for 2 days on this.

    struct NameNode
    {
    char* name;
    struct NameNode* next;
    };

    struct NameNode *head, *tail;

    void ReverseList()
    {
    // ?? this is killing me
    }
    Ivan

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    #define LAST 0
    #define PREV 1
    
    Node *get( Node *n, int g )
    {
        Node *o = n;
        while( o )
        {
            if( g == LAST && o->next == NULL ) break;
            if( g == PREV && o->next == n ) break;
            o = o->next;
        }
        return o;
    }
    
    Node *reverse( Node *n )
    {
        Node *o = get( n, LAST );
        Node *p = get( o, PREV );
        Node *q = o;
        while( p )
        {
            q->next = p;
            p = get( p, PREV );
            q = q->next;
        }
        return o;
    }
    Haven't tested it, but it's fairly slick looking, and I believe it should do the trick.

    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    You know what, I figure there are two really neat elegant ways to do this. First off, there's the recursive way...
    Code:
    Node * reverse (Node * n)
    {
     NODE * result = n;
     if (n -> next != NULL)
     {
      result = reverse (n -> next);
      n -> next -> next = n;
     }
     return result;
    }
    Basically, this function makes the last element point at the element before it, then that element points to the element before it, then that element points to the element before it, etc. Result just keeps track of the last node (or, after your list is finished being reversed, the first node, which is why we're keeping track of it). The only problem with this function is that it can't make the first node of the list point to it's parent, so it'd have to be called like....
    Code:
    Node * reverse2 (Node * n)
    {
     Node * result = reverse (Node * n);
     n -> next = NULL; // Because n is now the last node in the list
     return result;
    }
    The other way to do it is to use the last element of the list as a stack. So the code would go something like this...
    Code:
    Node * reverse (Node * n)
    {
     Node * p, * q, * result;
     p = n;
     for (result = n; result -> next != NULL; result = result -> next);
     for (; p != result;)
     {
      q = malloc (sizeof (Node));
      q -> next = result -> next;
      q -> info = p -> info;
      result -> next = q;
      q = p;
      p = p -> next;
      free (q);  
     }
     return result;
    }
    The first way just makes the pointers all point in the opposite direction, while the second one actually creates a new list backwards.
    Callou collei we'll code the way
    Of prime numbers and pings!

  5. #5
    Registered User ivandn's Avatar
    Join Date
    Oct 2001
    Posts
    49
    Thanks everyone for their help. I finally came up with some code to reverse the list i am happy with. Here it is in case you are curious.

    void ReverseList()
    {
    struct Node *a=NULL, *b=NULL, *i=tail=head;

    while (i){
    b = i->next;
    i->next = a;
    a = i;
    i = b;
    }

    head = a;
    }
    Ivan

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You know what, I figure there are two really neat elegant ways to do this. First off, there's the recursive way...
    code:
    Code:
    Node * reverse (Node * n)
    {
        NODE * result = n;
        if (n -> next != NULL)
        {
            result = reverse (n -> next);
            n -> next -> next = n;
        }
        return result;
    }
    I don't believe this works the way you expect, I could be slightly off here, but I think:

    node->node1->node2->node3->node4

    reverse(node)
    { node->next != null { r = reverse(node1)
    { node->next1 != null { r = reverse(node2)
    { node->next2 != null { r = reverse(node3)
    { node->next3 != null { r = reverse(node4) { return node4 }
    node3->node4->next=node3; return node4 }
    node4->node3->next=node4; return node4 }
    node4->node3->next=node4; return node4 }
    node4->node3->next=node4; return node4 }
    node4->node3->next=node4; return node4 }
    }

    I believe you end up with node4 being returned over and over, and the value not being set as expected, thus, you lose a chunk of the list?

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Without parameters, that function won't do anything!

    Code:
    void ReverseList()
    {
    struct Node *a=NULL, *b=NULL, *i=tail=head;
    while (i){
    b = i->next;
    i->next = a;
    a = i;
    i = b;
    }
    head = a;
    }
    __________________
    Ivan

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Without parameters, that function won't do anything!
    Actually, you're assuming local variable usage. Assume global variables for 'head' and 'tail'.

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    An array?

    Why not.


    Code:
    NODE *flip(NODE *head)
    {
    
     int nodeCount = CountNodes(head);  //<--To Do: write this
    
     NODE *handler[] = NewNode(nodeCount);
    
     NODE *traverse;  
     
     int i;
            
     handler[0] = head; // couldn't do this in loop
    
     for(traverse = head->next, i = 1; traverse->next != NULL, 
    i <= nodeCount; traverse = traverse->next,  i++)
    {
    handler[i] = traverse;
    handler[i]->next = handler[ i - 1];
    }
     
    return handler[nodeCount - 1];
    }
    Actually, I don't know if it will work.

    But one conspicuous problem is that the "handler" variable duplicates the memory, then is unable to deallocate it lest we lose all the data, i think.

  10. #10
    Unregistered
    Guest
    Actually, you're assuming local variable usage. Assume global variables for 'head' and 'tail'.
    Yuck, I guess your right.

    Total mistake, though.

  11. #11
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    I don't believe this works the way you expect, I could be slightly off here, but I think:
    4 is just passed back so we have some record of the new head, other than that, the return isn't meaningful. Really though, I think ivandn kinda hit the nail on the head with his answer, seeing it makes my answers quite dumb really.
    Callou collei we'll code the way
    Of prime numbers and pings!

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Yep, their answer is a nice on. I was going to try it recursivly, however, I don't believe you can do it with recursion and a single linked list. Consider the following source code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct nn {
    	struct nn * next;
    	int data;
    };
    
    struct nn * add( struct nn *n, int c )
    {
    	struct nn *no;
    	no = malloc( sizeof( struct nn ) );
    	no->data = c;
    	no->next = n;
    	return no;
    }
    
    void display( struct nn *n )
    {
    	struct nn *no;
    	for( no = n; no; no=no->next ) printf("%d:%c\n", no->data, no->data );
    }
    
    /** Here's your recursive method. **/
    
    struct nn * reverse (struct nn * n)
    {
     struct nn * result = n;
     if (n -> next != n )
     {
      result = reverse (n -> next);
      n -> next -> next = n;
     }
     return result;
    }
    
    int main( void )
    {
    	struct nn *list = NULL;
    	int c=-1;
    
    	while( c != 'Q' )
    	{
    		printf("Enter a letter and hit enter, Q to quit: ");
    		c = toupper( getchar( ) );
    		getchar( );
    
    		list = add( list, c );
    	}
    	printf("Displaying list:\n");
    	display( list );
    
    	printf("Reversing list.");
    	reverse( list );
    
    	printf("Displaying list:\n");
    	display( list );
    
    	return 0;
    }
    This program will bomb when it tries to run your recursive method. I don't think you can solve this with recursion. (I've tried myself briefly.)

    [edit]: don't feel bad, I added in my example, though admitidly, I hadn't tried it before I posted the code example, and it doesn't crash, but it does truncate the list to a single node! (mem leak) :P


    Quzah.
    Last edited by quzah; 12-17-2001 at 11:27 PM.
    Hope is the first step on the road to disappointment.

  13. #13
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    It really does work, it just isn't complete in itself. It needs the wrapper function, reverse2, and it's return must be saved as the new head of the list. Technically, these could probably be avoided by using a pointer to the head pointer, but pointers to pointers are not the friendliest things in the world...
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct _node
    {
     int info;
     struct _node * next;
    } Node;
    
    Node * reverse(Node * n);
    Node * reverse2(Node * n);
    void addNode (int i);
    
    int main ()
    {
     int i;
     Node * head = NULL;
     Node * p;
     for (i = 0; i < 5; i++)
     {
      p = malloc (sizeof(Node));
      p -> next = head;
      p -> info = i;
      head = p;
     }
     for (p = head; p != NULL; p = p -> next)
     {
      printf ("%d ", p -> info);
     }
    
     printf ("\n");
     
     head = reverse2 (head);
     for (p = head; p != NULL; p = p -> next)
     {
      printf ("%d ", p -> info);
     }
     return 0;
    }
    
    Node * reverse (Node * n)
    {
     Node * result = n;
     if (n -> next != NULL)
     {
      result = reverse (n -> next);
      n -> next -> next = n;
     }
     return result;
    }
    
    Node * reverse2 (Node * n)
    {
     Node * result = reverse (n);
     n -> next = NULL; // Because n is now the last node in the list
     return result;
    }
    Callou collei we'll code the way
    Of prime numbers and pings!

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Speaking of pointers to pointers...
    Code:
    int count( NODE *n )
    {
        NODE *o;
        int c=0;
    
        for(o=n;o;o=o->next) c++;
        return c;
    }
    
    NODE *reverse( NODE *n )
    {
        NODE *o;
        NODE **p;
        int c = count(n), x=0;
    
        if( c<1 ) { perror("Invalid list!"); exit( 0 ); }
    
        p = malloc( sizeof( NODE* ) );
        for(o=n;o;o=o->next) p[x++]=o;
        for(x;x>-1;x--)
            p[x]->next = p[x-1];
        p[0]->next = NULL;
        o = p[c-1];
        free( p );
        return o;
    }
    Right? That should work. If not, I've typo'd something, but the principle is right.

    Basicly, make an array of pointers, assigning each a node. Traverse it in reverse assigning that node's 'next' to the node in the array before it.

    Quzah.
    Last edited by quzah; 12-18-2001 at 04:28 PM.
    Hope is the first step on the road to disappointment.

  15. #15
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Well, anyway a singly-linked list is a bad structure.

    Use a doubly linked list.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Is it possible to 'reverse' a singly linked list?
    By Wiretron in forum C Programming
    Replies: 16
    Last Post: 05-08-2006, 04:50 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM