0

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;
            current = 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;
    }
silent
  • 2,836
  • 10
  • 47
  • 73

5 Answers5

3

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.

garph0
  • 1,700
  • 1
  • 13
  • 16
  • 1
    You are also leaking memory. In general, your reversing algorithm is not going to work. The best way to reverse a single linked list is to do it recursively: there also is a related question here on s.o.: http://stackoverflow.com/questions/2434411/linked-list-recursive-reverse – garph0 May 22 '10 at 09:59
  • There is also a simple iterative algorithm. See [Reverse a single chained List](http://stackoverflow.com/questions/1432205/reverse-a-single-chained-list). – Matthew Flaschen May 22 '10 at 10:29
1

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.

nc3b
  • 15,562
  • 5
  • 51
  • 63
0
void reverse(Node** list) {
    Node* previous=NULL;
    Node* current=*list;
    while (NULL!=current) {
        std::swap(previous, current->next);
        std::swap(previous, current);
    }
    *list=previous;
}
Ivan Tolstosheyev
  • 111
  • 9
0

Without checking your code I ask you this, are you sure that your linkedlist is working?

Marthin
  • 6,413
  • 15
  • 58
  • 95
-1

why not :

  1. measure the length of your list

  2. fill the append your list with zeros until you reach double the size of your existing list

  3. go to the beginning of the list,

  4. read contents one by one until you reach the end of the original list

  5. while moving on the original list:

  6. copy the contents of current node into the node having pointer advancing by

    ((original list length - current node index) * 2 + 1 ) * size of node

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

A.Rashad
  • 1,066
  • 12
  • 26
  • 1, 2, and 4 all take time proportional to the size of the list. 2 takes memory proportional to it. Also #6 seems to require moving backwards or repeatedly iterating to the desired index (quadratic). I don't think this algorithm is reasonable. – Matthew Flaschen May 22 '10 at 10:19
  • it should be something like this node+((max-idx)*2+1)*sizeof(node)=node->number; node++; – A.Rashad May 22 '10 at 10:23
  • You can't do pointer arithmetic. It's a linked list. Besides, pointer arithmetic handles the *sizeof* for you. – Matthew Flaschen May 22 '10 at 10:27