C++, O(n), No extra space, No modification of input lists, recursion; uses only call stack!


  • 0
    T
    class Solution {
    	using node = ListNode;
    
    	
    public:
    	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    	{
    		if (!l1 || !l2)
    			return l1 ? l1 : l2;
    
    		int len1{}, len2{};
    
    		len1 = findLength(l1);
    		len2 = findLength(l2);
    
    		node* newHead{};
    		node* tail{};
    		
    		if (len1 <= len2)
    			swap(l1, l2);
    
    		int carry{};
    
    		addTwoNumbersImpl(l1, l2, abs(len1 - len2), &tail, carry, &newHead,true);
    
    		return newHead;
    	}
    
    	int findLength(node* l1)
    	{
    		if (!l1) return 0;
    
    		int len{};
    		while (l1 = l1->next) len++;
    		
    		return len == 0 ? 1 : ++len;
    	}
    
    	void addTwoNumbersImpl(node* l1, node* l2, int psteps, node** tail, int& carry, node** newHead, bool isFirst=false)
    	{
    		if (!l1 || !l2) return;
    
    		if (psteps)
    			addTwoNumbersImpl(l1->next, l2, psteps-1, tail, carry, newHead);
    		else
    			addTwoNumbersImpl(l1->next, l2->next, psteps, tail, carry, newHead);
    
    		int currentSum;
    	        node* digit;
    	    
    		currentSum = (!psteps)?(carry + l1->val + l2->val):(carry + l1->val);
    
    		digit = new node(currentSum>9 ? currentSum % 10 : currentSum);
    		digit->next = (*tail);
    		(*tail) = digit;
    		*(newHead) = *tail;
    
    		carry = currentSum>9 ? currentSum / 10 : 0;
    
    		if (isFirst)
    			if (carry)
    			{
    				digit = new node(carry);
    				digit->next = (*tail);
    				(*tail) = digit;
    				*(newHead) = *tail;
    				return;
    			}
    			
    		return;
    	}
    
    };```

Log in to reply
 

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