Stuck on Linked List Reverse Function

[akebono]

Hi, I am stuck of a void function to reverse a linked list..
I looked around the web, and this function seems to always pop up:

void Reverse(struct node* head) {
   struct node* result = NULL;
   struct node* current = head;
   struct node* next;
   while (current != NULL) 
   {
     next = current->next;
     current->next = result;
     result = current;
     current = next;
   }
   head = result;
}

but, for some reason, this does not work as expected in my program.. I use the exact same function, but when i test it, it always displays the first node in the same order as before.. for example, I have 2 integer nodes with values of each one 2 and 3, but when i call the reverse function, and print out the nodes, it only shows Node 1 = 2 and there's no 3 at all..which doesn't make sense..

I also tried visualizing and drawing a picture of this function, and my result further confuses me, since it seems to not reverse the linked list at all!

My picture: [url]http://img27.imageshack.us/img27/8399/linkedlistreverse.png[/url]

I really need some help fast on this..

[herbert1910]

neat. the nodes are flipped by linking to previous nodes instead of next nodes.

      1->2->3->4->NULL
NULL<-1  2->3->4->NULL
NULL<-1<-2  3->4->NULL
NULL<-1<-2<-3  4->NULL
NULL<-1<-2<-3<-4

the result is the same as:

      4->3->2->1->NULL

the reverse part works, but you begin printing at the end (node 1) and hit NULL the first time:

1->NULL

you need the start of the new list (head).

you'd think this would work, but it doesn't:

#include <iostream>
using namespace std;

void nullmyiptr(int *iptr) {
	iptr = NULL; // iptr will change within the function
}

int main() {
	int i, *iptr;
	i = 99;
	iptr = &i;
	nullmyiptr(iptr); // doesn't change iptr
	if(iptr == NULL) cout << "iptr is NULL!" << endl;
	else cout << "iptr didn't change. wtf." << endl;
	return(0);
}

i suppose nullmyiptr(&i) doesn't make sense. maybe all we pass to the function is an address, and changes to that address are never returned?

your Reverse works ok if you return the location of the new start node. start printing your nodes at your returned result.

struct node* Reverse(struct node* head) {
   struct node* result = NULL;
   struct node* current = head;
   struct node* next;
   while (current != NULL) 
   {
     next = current->next;
     current->next = result;
     result = current;
     current = next;
   }
   return(result);
}

[akebono]

yes, but my function has to be a void function.. how would that work?
my main function would have the reverse function, then a function after that to print the nodes...

and i still don't understand how it reverses .. if i have 2 nodes with values 2 and 3, no matter how hard i try to visualize or draw the function, i end up with the order 2 and 3 again and not 3 and 2..

the way i think of it, next=current->next is 3, then result points to current, which is 2, and current points to next, which is 3... so it ends up in the same order again..

[akebono]

ohhh, it finally worked for me.. but it only worked if i put the print function in the reverse function..

how do i make the head in the reverse function a call by reference parameter that is a pointer to the head of the list?
i thought pointers were already call by reference..

[herbert1910]

ha ha. dude. you copied the code wrong.

void Reverse(struct node **refhead) {
   struct node* result = NULL;
   struct node* current = *refhead;
   struct node* next;
   while (current != NULL) 
   {
     next = current->next;
     current->next = result;
     result = current;
     current = next;
   }
   *refhead = result;
}

you need a pointer to your head to change your head in a function, so find or create your missing otherhead as a pointer to a pointer.

struct node **otherhead;
otherhead = &head;

Reverse(otherhead);

after that, you can just let your otherhead hang around because you don't need it. or you could use your otherhead in an add function. or use your otherhead all the time instead of your head by dereferencing: *otherhead. but that looks odd.

supposedly C++ can do something similar thing with &*, but i don't know how it works.

[herbert1910]

the function reverses the links. variables hold the links we change so we don't get lost.

the list:

node1->next = node2;
node1->num = 2;
node2->next = NULL;
node2->num = 3;

loop 1:

next = current->next;   // next = node1->next = location of node2
current->next = result; // node1->next = NULL (no previous node)
result = current;       // result = location of node1
current = next;         // current = location of node2 

the only thing we did to the list was:

node1->next = NULL

loop2:

next = current->next;   // next = node2->next = NULL (end of list)
current->next = result; // node2->next = location of node1 (previous node)
result = current;       // result = location of node2
current = next;         // current = NULL 

the only thing we did to the list was:

node2->next = node1

loop ends because we hit the end of the list.

result holds the location of the last node we worked on. node2.

node 2 is the new beginning, and node1 is now the end.

the list is reversed:

node2->next = node1;
node2->num = 3;
node1->next = NULL;
node1->num = 2;