The following code creates a linked list with 20 random elements, and then reverses the list.

/* reverse-linked-list.cpp Jason B. Hill (jason@jasonbhill.com) reverse a linked list in C++ */   #include <iostream> #include <cstdlib>   using namespace std;   // Node class class Node {   public: int data; Node* next;   // create a new node Node(int x, Node* addr) { data = x; next = addr; } };   // LinkedList class class LinkedList { private: Node* head;   public:   // initialize a linked list with a NULL head LinkedList() { head = NULL; }   // determine if a list is empty bool is_empty() { if(head == NULL) return 1; else return 0; }   // add an item to a linked list void node_add(int val) { if(head == NULL) head = new Node(val, NULL); else { Node* n = head; while(n->next != NULL) n = n->next; n->next = new Node(val, NULL); } }   // return the length of a linked list unsigned int length() { if(head == NULL) return 0; if(head->next == NULL) return 1; unsigned int len = 1; Node* n = head; while(n->next != NULL) { n = n->next; len++; } return len; }   // print a linked list void print() { cout<<"["; if(head != NULL) { if(head->next == NULL) cout<<head->data; else { Node* n = head; while(n->next != NULL) { cout<<n->data<<","; n = n->next; } cout<<n->data; } } cout<<"]\n"; }   //reverse a linked list void reverse() { if(head != NULL and head->next != NULL) { Node* m = head; Node* n = head->next; Node* t = NULL; if(n->next != NULL) t = n->next; head->next = NULL; while(t->next != NULL) { n->next = m; m = n; n = t; t = t->next; } n->next = m; head = t; t->next = n; } } };   int main(void){   LinkedList L; unsigned int i;   srand(time(NULL)); for(i=0;i<20;i++) L.node_add(rand() % 100);   L.print();   L.reverse();   L.print();     return(0); }

This can be compiled (using gcc/g++) using:

g++ reverse-linked-list.cpp -o reverse-linked-list

An example execution is:

\$ ./reverse-linked-list [99,31,17,41,7,38,59,7,67,75,75,13,62,70,0,20,46,3,14,24] [24,14,3,46,20,0,70,62,13,75,75,67,7,59,38,7,41,17,31,99]
Posted in C++

1. asas
Posted July 21, 2013 at 01:15 |

[Error] ‘time’ was not declared in this scope

What i do Now??

2. jason
Posted July 25, 2013 at 18:53 |

Try using an include for time.h in the header.

3. Posted January 19, 2019 at 18:37 |

I could be mistaken but it seems that your reverse function has an error in it. In the case where only 2 nodes are present in the list, the variable t will remain NULL as declared in the function beginning.

This will likely lead to a segmentation fault on the line :

 

 while(t->next != NULL)

 

Note that because t is NULL you cannot deference it using t->next.

when you check for n->next != NULL, you really don't need this check before assigning to t. If n->next is NULL then go ahead and assign it to t anyway since t is already NULL. This will eliminate an unnecessary check. For the 2 node case you will need to handle it slightly differently, and so need to check before the while loop whether t is NULL or not. If it is not then the code is great as is. However when t==NULL before iterating the while loop, you should avoid the while loop and simply set the head to n, and n->next to m. Here is an updated version. More elegant solutions likely exist.

 //reverse a linked list void reverse() { if(head != NULL and head->next != NULL) { Node* m = head; Node* n = head->next; Node* t = NULL; //if(n->next != NULL) t = n->next; head->next = NULL; if(t != NULL) { while(t->next != NULL) { n->next = m; m = n; n = t; t = t->next; } n->next = m; head = t; t->next = n; } else { n->next = m; head = n; } } } 

4. Posted August 10, 2019 at 01:27 |

Partager cette histoire Aimez-nous sur Facebook connexes Nouvelles Free Agents MLB 2014 Rumeurs: Pitcher Jon Lester Picking entre Boston Red Sox, Cubs de Chicago, San Francisco Giants, LA DodgersYankees Agent Nouvelles et rumeurs gratuit: Andrew Miller Nearing Deal With New York Joe Maddon, qui a fait son premier grand mouvement comme nouveau gérant des Cubs, a déclaré que Lester vaut le pari, que le lanceur agent libre a été leur top-cible depuis l’intersaison a commencé.