C++ solution by using stack.


  • 0

    emm.. it's not difficult to understand.
    O(n) time and O(n) space.

    /**
    * 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) {
          stack<int> stack1, stack2;
          ListNode *pscan1 = l1, *pscan2 = l2, *pnew, *last = NULL;
          
          while(pscan1 && pscan2)
          {
              stack1.push(pscan1->val);
              stack2.push(pscan2->val);
              
              pscan1 = pscan1->next;
              pscan2 = pscan2->next;
          }
          
          while(pscan1)
          {
              stack1.push(pscan1->val);
              pscan1 = pscan1->next;
          }
          
          while(pscan2)
          {
              stack2.push(pscan2->val);
              pscan2 = pscan2->next;
          }
          
          int carry = 0, temp = 0;
          while(!stack1.empty() && !stack2.empty())
          {
              temp = stack1.top() + stack2.top() + carry;
              carry = (temp > 9);
              
              pnew = new ListNode(temp % 10);
              pnew->next = last;
              last = pnew;
              
              stack1.pop();
              stack2.pop();
          }
          
          while(!stack1.empty())
          {
              temp = stack1.top() + carry;
              carry = (temp > 9);
              
              pnew = new ListNode(temp % 10);
              pnew->next = last;
              last = pnew;
              
              stack1.pop();
          }
          
          while(!stack2.empty())
          {
              temp = stack2.top() + carry;
              carry = temp > 9;
              
              pnew = new ListNode(temp % 10);
              pnew->next = last;
              last = pnew;
              
              stack2.pop();
          }
          
          if(carry != 0)
          {
              pnew = new ListNode(carry);
              pnew->next = last;
          }
          
          return pnew;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.