C++ O(n) time,O(n) space recursive solution without reverse


  • 0
    S
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        void add(ListNode*& head,int val)
        {
            ListNode* cur=new ListNode(val);
            if(!head) {head=cur;return;}
            cur->next=head;
            head=cur;
            return;
        }
        int get_len(ListNode* li)
        {
            int i=0;
            while(li) {i++;li=li->next;}
            return i;
        }
        void dfs(int len1,int len2,ListNode* l1,ListNode* l2,int& c,ListNode*& head)
        {
            int ca;
            if(!len1 && !len2)
            {
                c=0;
                return;
            }
            if(len1>len2)
            {
                dfs(len1-1,len2,l1->next,l2,ca,head);
                add(head,(l1->val+ca)%10);
                c=(l1->val+ca)/10;
                return;
            }
            if(len1<len2)
            {
                dfs(len1,len2-1,l1,l2->next,ca,head);
                add(head,(l2->val+ca)%10);
                c=(l2->val+ca)/10;
                return;
            }
            dfs(len1-1,len2-1,l1->next,l2->next,ca,head);
            add(head,(l1->val+l2->val+ca)%10);
            c=(l1->val+l2->val+ca)/10;
            return;
        }
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            int i;
            if(!l1) return l2;
            if(!l2) return l1;
            int len1=get_len(l1);
            int len2=get_len(l2);
            ListNode* head=NULL;
            int c;
            dfs(len1,len2,l1,l2,c,head);
            if(c) add(head,c);
            return head;
        }
    };
    

Log in to reply
 

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