SHARE
TWEET

Untitled

bbescos Feb 3rd, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. // why struct rather than class?
  7. // usually structs are used for simpler things even
  8. // though you can define functions withins structs too
  9. // difference: in structs, everything is public by default
  10. // in classes, everything is private by default
  11. struct ListNode{
  12.     int val;
  13.     ListNode* next;
  14.     ListNode(int val) : val(val), next(nullptr) {}
  15. };
  16.  
  17. // when creating a new node you need to allocate memory storage for it
  18. // ListNode* head = ListNode(0);
  19. // head points nowhere, since ListNode(0) is not stored. ListNode(0) is automatically destroyed.
  20. // ListNode node(0);
  21. // head = &node;
  22. // new solves this issue:
  23. // ListNode* head = new ListNode(0);
  24. ListNode* vec2list(const std::vector<int>& vec) {
  25.    
  26.     if (vec.empty())
  27.         return nullptr;
  28.    
  29.     ListNode* head = new ListNode(vec[0]);
  30.     ListNode* current = head;
  31.    
  32.     for (int i = 1; i < vec.size(); ++i) {
  33.         ListNode* next = new ListNode(vec[i]);
  34.         current->next = next;
  35.         current = current->next;
  36.     }
  37.  
  38.     return head;
  39. }
  40.  
  41. void printLinkedList(ListNode* head) {
  42.    
  43.     while (head) {
  44.         std::cout << head->val << " ";
  45.         head = head->next;
  46.     }
  47.     std::cout << std::endl;
  48. }
  49.  
  50. void deleteNode (ListNode* head, int num) {
  51.    
  52.     ListNode* current = head;
  53.     ListNode* prev = nullptr;
  54.    
  55.     int i = 0;
  56.     while (current) {
  57.         if (i == num) {
  58.             prev->next = current->next;
  59.             delete current;
  60.             break;
  61.         }
  62.         prev = current;
  63.         current = current->next;
  64.         ++i;
  65.     }
  66. }
  67.  
  68. // Run-time complexity O(1)
  69. void deleteNode (ListNode* current) {
  70.    
  71.     ListNode* next = current->next;
  72.    
  73.     current->val = next->val;
  74.     current->next = next->next;
  75.     delete next;
  76.  
  77. }
  78.  
  79. ListNode* reverseList(ListNode* head) {
  80.        
  81.     ListNode* prev = nullptr;
  82.     ListNode* current = head;
  83.     ListNode* next = nullptr;
  84.  
  85.     while(current) {
  86.         next = current->next;
  87.         current->next = prev;
  88.         prev = current;
  89.         current = next;
  90.     }
  91.  
  92.     head = prev;
  93.  
  94.     return head;
  95. }
  96.  
  97. int main(){
  98.    
  99.     ListNode my_list_node(5);
  100.    
  101.     std::vector<int> my_vec_of_ints = {1,2,3,4,5,6};
  102.    
  103.     ListNode* my_linked_list = vec2linkedlist(my_vec_of_ints);
  104.    
  105.     printLinkedList(my_linked_list);
  106.    
  107.     deleteNode(my_linked_list, 2);
  108.    
  109.     printLinkedList(my_linked_list);
  110.    
  111.     deleteNode2(my_linked_list->next->next);
  112.    
  113.     printLinkedList(my_linked_list);
  114.    
  115.     my_linked_list = reverseList(my_linked_list);
  116.    
  117.     printLinkedList(my_linked_list);
  118.    
  119.     return 0;
  120. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top