add-two-numbers.cpp (3438B)
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 //This problem was to take the values in two different singly 5 //linked lists and add the values together in each index. The lists were in reverse order 6 //so as you move to the right the values greater than 10 are carried to the right(As opposed to 7 //carrying 10s to the left which is the normal way we count). 8 9 //Leetcode: 10 //Speed: 27ms Beats: 93.80% 11 //Memory: 70.8MB Beats: 99.41% 12 //This was a challenge but I learned a lot about pointers and instantiating objects. 13 14 //Output: 15 //Added Lists: 16 //0 3 6 0 5 0 9 1 17 // 18 19 20 //This is the structure of a single node of the linked list 21 //it contains the value of the current node and a pointer to the next one. 22 struct ListNode { 23 int val; 24 ListNode *next; 25 }; 26 27 28 //Takes an input which are ponters to the first node of a list. 29 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { 30 31 //Need refrence to the first node because there is no way 32 //back to the start once you start iterating the list. 33 ListNode* first_node = l1; 34 int carry = 0; 35 ListNode* last_pointer; 36 while(l1 != NULL and l2 != NULL){ 37 l1->val = l1->val + l2->val + carry; 38 carry = l1->val / 10; 39 l1->val = l1->val % 10; 40 l2 = l2->next; 41 last_pointer = l1; 42 l1 = l1->next; 43 } 44 //This runs if the first list is longer than the second. 45 while (l1 != NULL){ 46 l1->val = l1->val + carry; 47 carry = l1->val / 10; 48 l1->val = l1->val % 10; 49 last_pointer = l1; 50 l1 = l1->next; 51 } 52 //This runs if the second list is longer than the first. 53 while(l2 != NULL){ 54 ListNode* next_ptr = new ListNode(); 55 last_pointer->next = next_ptr; 56 last_pointer = next_ptr; 57 next_ptr->val = (carry + l2->val) % 10; 58 carry = (l2->val + carry) / 10; 59 l2 = l2->next; 60 } 61 //This runs at the end if the lists are completely walked, but there is still a value 62 //being carried 63 if(carry != 0){ 64 ListNode* ln_last = new ListNode(); 65 ln_last->val = carry; 66 (*last_pointer).next = ln_last; 67 } 68 return first_node; 69 } 70 71 72 int main(){ 73 74 //Creates the first node and sets up the necessary refrences to it 75 //in order to iterate through it, but still pass it as a pointer from 76 //the first node. 77 ListNode* l1 = new ListNode(); 78 ListNode* l2 = new ListNode(); 79 ListNode* first = l1; 80 ListNode* second = l2; 81 ListNode* itr1 = l1; 82 ListNode* itr2 = l2; 83 //Initialize the values to be saved to the list. I could have done this using an array 84 //but arrays don't have a size function so it is kind of a hassle. You need to do some 85 //math to find the length of them based on the size of each index. 86 vector<int> vals = {0, 2, 3, 5, 6, 7, 9}; 87 vector<int> vals2 = {0, 1, 3, 5, 8, 2, 9}; 88 for(int i = 0 ; i < vals.size(); ++i){ 89 itr1 = new ListNode(); 90 itr2 = new ListNode(); 91 l1->next = itr1; 92 l2->next = itr2; 93 l1->val = vals[i]; 94 l2->val = vals2[i]; 95 l1 = l1->next; 96 l2 = l2->next; 97 } 98 //This runs the function and assigns the output 99 ListNode* added_vals = addTwoNumbers(first, second); 100 cout << "Added Lists: " << endl; 101 //This prints out the output 102 while (added_vals != NULL){ 103 cout << added_vals->val << " "; 104 added_vals = added_vals->next; 105 } 106 cout << endl; 107 return 0; 108 109 }