I'm trying to reverse a linked list and save it into another new liked list and delete the old one, but I get an error when compiling.. Here's the function..
LinkedList LinkedList::reverse(){
LinkedList L2;
Node * temp=head;
while(temp->next!=NULL){
Node * del=NULL;
L2.addAtFront(temp->data);
del=temp;
temp=temp->next;
delete del;
}
return L2;
}
Use this if (and only if) you no longer need the original linked list!
Instead of using addAtFront which is less cheap (because you need to allocate memory for new nodes and destroy the old ones), you can reuse the nodes and the LinkedList (after all, you were going to delete the original one, and simply set the pointers:
LinkedList LinkedList::reverse(){
Node* na = head;
Node* nb = NULL;
Node* nc = NULL;
if(na == NULL) {
return this;
}
nb = na->next;
na->next = NULL;
while(nb != NULL){
nc = nb->next;
nb->next = na;
na = nb;
nb = nc;
}
tail = head; //if you keep a tail?
head = na;
return this;
}
The method works as follows, you scan over the original list and use three references: na, nb and nc. Who are organized in the order of the original list.
Now you know for sure na and nb are effective in the while loop. You first ensure that you will keep a reference to nb's next by storing it in nc. Next you set the ->next of nb to na (originally na->next was nb), so now it is reversed.
Then you shift in the process: na becomes the old nb, nb the old nc. You keep repeating this until you reach the end of the linked list.
You need to do two additional tasks:
- Set the original head's ->next to null, otherwise you will construct a cycle; and
- Set the tail of the original LinkedList to the head.
If you maintain a tail, you will first need to set it to the head.
