Advertisement
xTheEc0

Reverse a linked list

Feb 14th, 2017
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3.  
  4. struct Node {
  5.     int data;
  6.     Node* next;
  7. };
  8.  
  9. Node* create_node(int node_data){
  10.    
  11.     //Create the node.
  12.     Node* n = new Node();
  13.    
  14.     //Set the data.
  15.     n->data = node_data;  
  16.    
  17.     return n;
  18. }
  19.  
  20. //Create a new node and set the inputted node's next pointer
  21. //to the new node. Returns a reference to the new node.
  22. Node* push_node(Node* curr, int node_data){
  23.    
  24.     if(curr == NULL){
  25.         return NULL;  
  26.     }
  27.    
  28.     Node* n = create_node(node_data);
  29.    
  30.     //Set the next pointer of the current node to the new node.
  31.     curr->next = n;
  32.    
  33.     return n;
  34. }
  35.  
  36. //Creates a linked list with the number of nodes equal to the inputted size.
  37. //Node data is set to 0, 1, 2, ... through "N" sequentially.
  38. //Returns a reference to the head of the list.
  39. Node* create_linked_list(int size){
  40.    
  41.     if(size < 1){
  42.         return NULL;  
  43.     }
  44.    
  45.     Node* head = create_node(0);
  46.     Node* curr = head;
  47.    
  48.     for(int i = 1; i < size; i++){
  49.         curr = push_node(curr, i);
  50.     }
  51.    
  52.     return head;
  53. }
  54.  
  55. void print_linked_list(Node* head){
  56.  
  57.     Node* curr = head;
  58.  
  59.     while(curr != NULL){
  60.        std::cout << curr->data;
  61.        curr = curr->next;
  62.     }
  63.    
  64.     std::cout << std::endl;
  65. }
  66.  
  67. void reverse_list(Node** head){
  68.    
  69.     Node* prev = nullptr;
  70.     Node* next = nullptr;
  71.     Node* curr = *head;
  72.  
  73.     while(curr != nullptr)
  74.     {
  75.         next = curr -> next;
  76.         curr -> next = prev;
  77.         prev = curr;
  78.         curr = next;
  79.     }
  80.  *head = prev;
  81. }
  82.  
  83. int main()
  84. {
  85.     Node* head = create_linked_list(10);
  86.     print_linked_list(head);
  87.    
  88.     //You should see: 0123456789
  89.    
  90.     reverse_list(&head);
  91.     print_linked_list(head);
  92.    
  93.     //You should see: 9876543210
  94.    
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement