Leetcode Add Two Numbers II problem solution

by

In this Leetcode Add Two Numbers II problem solution, You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Leetcode Add Two Numbers II problem solution

Problem solution in Python.

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        def getValueFromList(list_node):
            value = 0
            while list_node:
                value = 10 * value + list_node.val
                list_node = list_node.next
            return value

        def splitIntToValues(value):
            if not value:
                return [value]
            
            result = []
            while value:
                result.append(value % 10)
                value //= 10
            return result[::-1]
        
        def getListFromValues(values):
            prehead = ListNode()
            prev = prehead
            
            for value in values:
                node = ListNode(value)
                prev.next = node
                prev = prev.next
            
            return prehead.next
        
        resultValue = getValueFromList(l1) + getValueFromList(l2)
        return getListFromValues(splitIntToValues(resultValue))

Problem solution in Java.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> l1Stack = new Stack<>();
        Stack<Integer> l2Stack = new Stack<>();
        
        while(l1 != null)
        {
            l1Stack.push(l1.val);
            l1 = l1.next;
        }
        
        while(l2 != null)
        {
            l2Stack.push(l2.val);
            l2 = l2.next;
        }
        
        ListNode cur = null;
        ListNode prev = null;
        int carry = 0;
        
        while(!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry == 1)
        {
            int l1Val = (l1Stack.isEmpty() ? 0 : l1Stack.pop());
            int l2Val = (l2Stack.isEmpty() ? 0 : l2Stack.pop());
            
            int sum = l1Val + l2Val + carry;
            carry = 0;
            if(sum >= 10)
            {
                carry = 1;
                sum = sum % 10;
            }
            
            if(prev == null)
            {
                prev = new ListNode(sum);
            }
            else
            {
                cur = prev;
                prev = new ListNode(sum);
                prev.next = cur;
            }
        }
        
        return prev;
    }

Problem solution in C++.

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int n=0, i, carry=0;
        string str1,str2,str;
        ListNode *node;
        node = l1;
        while(node)
        {
            str1.push_back(node->val+'0');  //int to string
            node = node->next;
        }
        node = l2;
        while(node)
        {
            str2.push_back(node->val+'0');
            node = node->next;
        }
  
        if(str1.size()> str2.size())
            str2.insert(0, str1.size()-str2.size(), '0');
        else if(str2.size() > str1.size())
            str1.insert(0, str2.size()-str1.size(), '0');
  
        i=str1.size()-1;
        while(i>=0)
        {
            n = (str1[i]-'0')+(str2[i]-'0')+carry;
            if(n>9)
                carry = n/10;
            else
                carry =0;
            str.push_back(n%10+'0');
            i--;
        }
        if(carry > 0)
            str.push_back(carry+'0');
 
        ListNode *l = new ListNode();
        node = l;
        i=str.size()-1;
        while(i>=0)
        {
            node->next = new ListNode(str[i]-'0');  //string to int
            node = node->next;
            i--;
        }
        return l->next;
    }

Problem solution in C.

char* addition(const char* add1, int length1, const char* add2, int length2)
{
    int i, flag = 0, diff = length1 - length2;;
    char* output = (char*)malloc(length1 + 1);
    for (i = length1 - 1; i >= diff; i--)
    {
        int tempdigi, tail1, tail2;
        tail1 = add1[i];
        tail2 = add2[i - diff];
        tempdigi = tail1 + tail2 + flag;
        flag = 0;
        if (tempdigi >= 10)
        {
            tempdigi -= 10;
            flag = 1;
        }
        output[i + 1] = tempdigi;
    }
    //copy the remaining digits
    if (diff > 0)
    {
        i = diff - 1;
        while (i >= 0)
        {
            int tempdigi = add1[i] + flag;
            flag = 0;
            if (tempdigi >= 10)
            {
                tempdigi %= 10;
                flag = 1;
            }
            output[i + 1] = tempdigi;
            i--;
        }
    }
    if (flag == 1)
        output[0] = 1;
    else output[0] = 'x';
    return output;
}

int countlinklist(struct ListNode* list)
{
    int count = 0;
    while (list != NULL)
    {
        count++;
        list = list->next;
    }
    return count;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    struct ListNode *output = (struct ListNode*)malloc(sizeof(struct ListNode));
    char* arr1 = (char*)malloc(countlinklist(l1));
    char* arr2 = (char*)malloc(countlinklist(l2));
    int count1 = 0, count2 = 0;
    while (l1 != NULL)
    {
        arr1[count1] = l1->val;
        count1++;
        l1 = l1->next;
    }
    while (l2 != NULL)
    {
        arr2[count2] = l2->val;
        count2++;
        l2 = l2->next;
    }
    char* sum;
    if (count1 >= count2)
        sum = addition(arr1, count1, arr2, count2);
    else
        sum = addition(arr2, count2, arr1, count1);
    int len = 1 + (count1 > count2 ? count1 : count2);
    int i = 0;
    while ((sum[i] == 0 || sum[i]=='x') && i < len)
        i++;
    if (i == len)
    {
        output->val = 0;
        output->next = NULL;
        return output;
    }
    output->val = sum[i];
    i++;
    struct ListNode *last = output;
    while (i < len)
    {
        struct ListNode* nextNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        last->next = nextNode;
        last = nextNode;
        nextNode->val = sum[i];
        i++;
    }
    free(sum);
    free(arr1);
    free(arr2);
    last->next = NULL;
    return output;
}