Sunday, July 19, 2015

Leetcode: Add two numbers: complete project codes in C++ with detail comments

The key points in this problem:

1. linked list
2. how to build a linked listed in run time
For the second problem, you need to understand the following two line of codes:
//create new node in run time and change the pointer in tail
p_result_tmp->next = new ListNode(tmp);
p_result_tmp = p_result_tmp->next;

As in list struct,
  p_result_tmp->val   is the value 
 p_result_tmp->next  is the pointer to the linked list
 p_result_tmp        is the pointer/address to itself 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


//////////////////////////////////////////////////////////////////
//Add Two Numbers
//////////////////////////////////////////////////////////////////

# include "stdafx.h"
# include <cstdlib>
# include <iostream>     // std::cout


using namespace std;


/////////////////////////////////////////////
//Add Two Numbers
/////////////////////////////////////////////
//Definition for singly-linked list.
 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

class Solution {
public:
       ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
              ListNode* p1;
              ListNode* p2;

              ListNode* p_result;
              p_result = new ListNode(0);

              ListNode* p_result_tmp;
              p_result_tmp = p_result;

              int add_tmp=0;
              int tmp = 0;
              int c=0;
              p1 = l1;
              p2 = l2;
              // using while loop as the length of list is not known ahead
              while (p1!=NULL || p2!=NULL){
           
                     if (p1 != NULL && p2 != NULL){
                            add_tmp = p1->val + p2->val+c;
                           c = add_tmp > 9 ? 1 : 0;
                           tmp = c == 0 ? add_tmp : add_tmp % 10;
                           //creat new node in run time and change the pointer in tail
                           p_result_tmp->next = new ListNode(tmp);
                           p_result_tmp = p_result_tmp->next;

                           //pointer control
                           p1 = p1->next;
                           p2 = p2->next;
                     }
                     else{
                           tmp = p1 != NULL ? p1->val + c : p2->val + c;
                           //check whether tmp >=10
                           c = tmp > 9 ? 1 : 0;
                           tmp = c == 0 ? tmp : tmp % 10;//take second digit
                           p_result_tmp->next = new ListNode(tmp);
                           p_result_tmp = p_result_tmp->next;
                           //pointer control
                           if (p1 != NULL){
                                  p1 = p1->next;
                           }
                           else{
                                  p2 = p2->next;
                           }
                     }
              }
              //the condition when input is like [5], [5]
              if (c == 1){
                     p_result_tmp->next = new ListNode(1);
                     p_result_tmp = p_result_tmp->next;
              }
              p_result = p_result->next;//exclude the first one
              return p_result;

       }
};



int main(int argc, char *argv[])

{
       ListNode* l1; //define a pointer that points to struct
       l1 = new ListNode(9);//assign a value to the pointer
       l1->next = new ListNode(9);//assign a value to the next linked pointer


       ListNode* l2;
       l2 = new ListNode(1);// why need new??
       l2->next = new ListNode(9);
       l2->next->next = new ListNode(8);

       Solution s;
       ListNode* result;
       result = s.addTwoNumbers(l1,l2);
      

       cout << "the solution is";
       cout << result->val;

       cout << "  Hello, world!\n";

       int age;
       cin >> age;

       return 0;
}



No comments:

Post a Comment