Can anyone reverse a singly linked list in a graceful manner?
Thank you for your help.
Can anyone reverse a singly linked list in a graceful manner?
Thank you for your help.
Ivan
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
Haven't tested it, but it's fairly slick looking, and I believe it should do the trick.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; }
Quzah.
Hope is the first step on the road to disappointment.
You know what, I figure there are two really neat elegant ways to do this. First off, there's the recursive way...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 * reverse (Node * n) { NODE * result = n; if (n -> next != NULL) { result = reverse (n -> next); n -> next -> next = n; } 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 * reverse2 (Node * n) { Node * result = reverse (Node * n); n -> next = NULL; // Because n is now the last node in the list 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.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; }
Callou collei we'll code the way
Of prime numbers and pings!
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
I don't believe this works the way you expect, I could be slightly off here, but I think: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; }
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.
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
Actually, you're assuming local variable usage. Assume global variables for 'head' and 'tail'.Without parameters, that function won't do anything!
Quzah.
Hope is the first step on the road to disappointment.
An array?
Why not.
Actually, I don't know if it will work.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]; }
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.
Yuck, I guess your right.Actually, you're assuming local variable usage. Assume global variables for 'head' and 'tail'.
Total mistake, though.
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.I don't believe this works the way you expect, I could be slightly off here, but I think:
Callou collei we'll code the way
Of prime numbers and pings!
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:
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.)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; }
[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.
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!
Speaking of pointers to pointers...
Right? That should work. If not, I've typo'd something, but the principle is right.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; }
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.
Well, anyway a singly-linked list is a bad structure.
Use a doubly linked list.