Create a reverse LinkedList in C ++ from this LinkedList

Question

I am having trouble creating a linked list in reverse order from a specific linked list.

I come from a java background and just started making C ++.

Can you check my code and see what is wrong? I assume that I am simply manipulating the pointer and not creating anything new.

//this is a method of linkedlist class, it creates a reverse linkedlist //and prints it void LinkedList::reversedLinkedList() { Node* revHead; //check if the regular list is empty if(head == NULL) return; //else start reversing Node* current = head; while(current != NULL) { //check if it the first one being added if(revHead == NULL) revHead = current; else { //just insert at the beginning Node* tempHead = revHead; current->next = tempHead; revHead = current; } current = current->next; }//end while //now print it cout << "Reversed LinkedList: " << endl; Node* temp = revHead; while(temp != NULL) { cout << temp->firstName << endl; cout << temp->lastName << endl; cout << endl; temp = temp->next; } }//end method 

Answer 1

Easier: go to your list, save the previous and next node and just point the current node to the previous one:

 void LinkedList::reversedLinkedList() { if(head == NULL) return; Node *prev = NULL, *current = NULL, *next = NULL; current = head; while(current != NULL){ next = current->next; current->next = prev; prev = current; current = next; } // now let the head point at the last node (prev) head = prev; } 

Answer 2

 Node* revHead; // ... while(current != NULL) { //check if it the first one being added if(revHead == NULL) 

You do not initialize revHead , but use it. (I hope it’s already clear to you that revHead is a local variable used to store a memory address, not something that exists outside of a method / procedure)

The revHead storage revHead is automatic (also in the local teleobject). In C++ , when you make such an announcement, there is no guarantee that the value will be 0 .

(if the storage class is not of the static type or the global variable, where it is automatically initialized to 0 , unless another value is specified. In your case, the variable has the storage class of the auto type, which means that it is locally defined in the function, and when the local variable is declared without specifying a value, this value is garbage. Keep in mind that with the next C ++ C++0x auto keyword has a new meaning).

The value in your case is garbage, which causes the if crash. Read more here: Link

Do

 Node* revHead = NULL; 

Keep in mind that you may have errors like this in another part of your code.

Answer 3

Another method would be to first cross the list and save all the data on the stack, and then create a new list and paste the data from the top of the stack into it. The LIFO rack will provide you with data in the reverse order and therefore you will have a reverse list.

Answer 4

This is done using only two temporary variables.

 Node* list::rev(Node *first) { Node *a = first, *b = first->next; while(a->next!=NULL) { b = a->next; a->next = a->next->next; b->next = first; first = b; } return first; } 

Alternatively, you can do this using recursion.

Answer 5

 NODE * ReverseLinkedList(NODE * head){ if (head == NULL) return NULL; NODE * previous = NULL; while (head != NULL) { // Keep next node since we trash the next pointer. NODE *next = head->pNext; // Switch the next pointer to point backwards. head->pNext = previous; // Move both pointers forward. previous = head; head = next; } return previous; } 

Answer 6

I'm not sure, but I think you need a double list, where node has the next and previous. It will not work with an external pointer to a list. You will not have the address of the previous node.

If you are not using the above method with a stack, this is a good suggestion.

Answer 7

The above is a link to a list of links

 void LinkList::rev() { if(pFirst == NULL) return; ListElem *prev = NULL, *current = NULL, *next = NULL; current = pFirst; while(current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } // now let the head point at the last node (prev) pFirst = prev; } 

Answer 8

The example below uses recursion to modify the list of links. I asked this question at an interview. This has been tested and works. ListElem is a node.

 void LinkList::reverse() { if(pFirst == NULL) return; ListElem* current = pFirst; revCur(NULL, current, NULL); } void LinkList::revCur(ListElem *prev, ListElem* current, ListElem* next) { // ListElem *prev = NULL, *current = NULL, *next = NULL; if ( current != NULL ) { next = current->next; current->next = prev; prev = current; current = next; pFirst = prev; this->revCur(prev,current,next); } } 

Answer 9

  #include <stdint.h> /* this is a generic (structure agnostic) routine for reversing a singly linked list. 1st argument is the memory address the structure is located at, and 2nd argument is the memory address to this particular structure NEXT member. */ void *rsll(void *struct_address, void *next_address /*(void **)*/) { uint32_t offset, holder; offset = next_address - struct_address; void **p = struct_address, *progress = NULL; while(p) { void *b; holder = (uint32_t)p; holder += offset; p = (void**)holder; //&(N->next) b = *p; //(N->next) *p = progress; //(N->next) holder = (uint32_t)p; holder -= offset; p = (void**)holder; //N progress = p; p = b; } return progress; } #include <stdio.h> int main() { struct list_t { int integer; struct list_t *next; }; struct list_t d = {40,NULL}, c = {30,&d}, b = {23,&c}, a = {10,&b}; struct list_t *list; list = &a; list = rsll(list,&(list->next)); while(list) { printf("%d\n",list->integer); list = list->next; } return 0; }