Tutorial :reverse a linked list? [duplicate]



Question:

This question already has an answer here:

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


Solution:1

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.


Solution:2

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.


Solution:3

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


Solution:4

void reverse(Node** list) {      Node* previous=NULL;      Node* current=*list;      while (NULL!=current) {          std::swap(previous, current->next);          std::swap(previous, current);      }      *list=previous;  }  


Solution:5

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)


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »