My recursive CPP code without reversing the list


  • 0

    My recursive CPP code:
    Basic idea is to use call stack to get the carry from the following nodes.

    
    class Solution {
    public:
    	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    	{
    		int s1, s2;
    		ListNode *currL = l1, *currR = l2;
    		for (s1 = 0; currL; currL = currL->next, ++s1);
    		for (s2 = 0; currR; currR = currR->next, ++s2);
    		if (s1 < s2)
    			swap(l1, l2), swap(s1, s2);
    		if (addHelper(l1, l2, s1, s2))
    		{
    			ListNode *node = new ListNode(1);
    			node->next = l1;
    			l1 = node;
    		}
    		return l1;
    	}
    	int addHelper(ListNode *l1, ListNode *l2, int count1, int count2)
    	{
    		if (!l1)
    			return 0;
    		int q;
    		if (count1 > count2)
    			l1->val += addHelper(l1->next, l2, count1 - 1, count2);
    		else
    		{
    			l1->val += l2->val;
    			l1->val += addHelper(l1->next, l2->next, count1 - 1, count2 - 1);
    		}
    		q = l1->val / 10;
    		l1->val %= 10;
    		return q == 1;
    	}
    };

Log in to reply
 

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