https://leetcode.com/problems/add-two-numbers-ii/

1. Use recursion:

  1. //36 ms    70.6 MB
  3. /**
  4.  * Definition for singly-linked list.
  5.  * struct ListNode {
  6.  *     int val;
  7.  *     ListNode *next;
  8.  *     ListNode() : val(0), next(nullptr) {}
  9.  *     ListNode(int x) : val(x), next(nullptr) {}
  10.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  16.         if(!l1) return l2;
  17.         else if(!l2) return l1;
  19.         ListNode* curr1 = l1; 
  20.         ListNode* curr2 = l2; 
  21.         ListNode* result = NULL;
  23.         int len1 = 0, len2 = 0;
  24.         while(curr1){ curr1=curr1->next; len1++; }
  25.         while(curr2){ curr2=curr2->next; len2++; } 
  27.         curr1 = l1; curr2 = l2;
  29.         while(len1 > 0 && len2 > 0){
  30.             int sum = 0;
  31.             if(len1 >= len2){ 
  32.                 sum += curr1->val; curr1=curr1->next; len1--;
  33.             }
  34.             if(len2 > len1){ 
  35.                 sum += curr2->val; curr2=curr2->next; len2--;
  36.             }
  37.             result = addToFront(sum, result);
  38.         }
  40.         curr1 = result; 
  41.         result = NULL;
  42.         int carry = 0;
  44.         while(curr1){
  45.             curr1->val += carry; 
  46.             carry = curr1->val / 10;
  47.             result = addToFront( curr1->val % 10, result);
  48.             curr2 = curr1; 
  49.             curr1 = curr1->next;
  50.             delete curr2;
  51.         }
  52.         if(carry) 
  53.             result = addToFront(1, result);
  55.         return result;
  56.     }
  58. private:
  59.     ListNode* addToFront(int val, ListNode* head){
  60.         ListNode* temp = new ListNode(val);
  61.         temp->next = head;
  62.         return temp;
  63.     }
  64. };