# Thread: reverse a singly linked list

1. ## reverse a singly linked list

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

Thank you for your help.

2. 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
}

3. 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.

4. 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.

5. 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;
}

6. 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.

7. ## 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. Without parameters, that function won't do anything!
Actually, you're assuming local variable usage. Assume global variables for 'head' and 'tail'.

Quzah.

9. 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. Actually, you're assuming local variable usage. Assume global variables for 'head' and 'tail'.
Yuck, I guess your right.

Total mistake, though.

11. 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.

12. 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.)

: 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.

13. 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;
}```

14. 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.

15. Well, anyway a singly-linked list is a bad structure.

Use a doubly linked list.

Popular pages Recent additions