reverse a linked list? [duplicate]
Im trying to reverse the order of the following linked list, I've done so, But the reversed list does not seem to print out. Where have I gone wrong?
//reverse the linked list
#include <iostream>
using namespace std;
struct node{
int number;
node *next;
};
node *A;
void addNode(node *&listpointer, int num){
node *temp;
temp = new node;
temp->number = num;
temp->next = listpointer;
listpointer = temp;
}
void reverseNode(node *&listpointer){
node *temp,*current;
current = listpointer;
temp = new node;
while (true){
if (current == NULL){
temp = NULL;
break;
}
temp->number = current->number;
cur开发者_如何学Pythonrent = current->next;
temp = temp->next;
}
listpointer = temp;
}
int main(){
A = NULL;
addNode(A,1);
addNode(A,2);
addNode(A,3);
while (true){
if (A == NULL){break;}
cout<< A->number << endl;
A = A->next;
}
cout<< "****" << endl;
reverseNode(A);
while (true){
if (A == NULL){break;}
cout<< A->number << endl;
A = A->next;
}
cout<< "****"<< endl;
return 0;
}
Well, the first thing I notice is that you are doing
temp = new node
and then, on every interaction:
temp = temp->next
but you are never assigning temp->next
so when you finally override the list pointer you are surely giving back some funny value.
You do this:
while (true){
if (current == NULL){
temp = NULL;
break;
}
temp->number = current->number;
current = current->next;
temp = temp->next;
}
Suppose it works as you intended. When the while exists, temp
will be NULL
, right ?
listpointer = temp; <=> listpointer = NULL;
So this might be a problem.
Without checking your code I ask you this, are you sure that your linkedlist is working?
void reverse(Node** list) {
Node* previous=NULL;
Node* current=*list;
while (NULL!=current) {
std::swap(previous, current->next);
std::swap(previous, current);
}
*list=previous;
}
why not :
measure the length of your list
fill the append your list with zeros until you reach double the size of your existing list
go to the beginning of the list,
read contents one by one until you reach the end of the original list
while moving on the original list:
copy the contents of current node into the node having pointer advancing by
((original list length - current node index) * 2 + 1 ) * size of node
after you are done, get the pointer of the first node after your original list to point at a reversed list
without having to create a new list or to work on multiple iterations or to modify the existing data structure (not converting it into a double linked list)
精彩评论