1561/1563 test cases passed
problem discription:
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. link to problem: https://leetcode.com/problems/add-two-numbers-ii/
you dont need to provide me with code(would be helpful), just the answer why do I get wrong answer for next questions.
void insert_begging(struct ListNode **root,unsigned __int128 val){
struct ListNode *new_node = malloc(sizeof(struct ListNode));
new_node->val = val;
if(*root == NULL){
new_node->next = NULL;
*root = new_node;
return;
}
new_node->next = *root;
*root = new_node;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* result = NULL;
struct ListNode* curr = l1;
unsigned __int128 sum = 0;
unsigned __int128 sum2 = 0;
while(curr!=NULL){
sum=sum*10+curr->val;
curr=curr->next;
}
struct ListNode* curr2 = l2;
while(curr2!= NULL){
sum2=sum2*10+curr2->val;
curr2=curr2->next;
}
unsigned __int128 rsum = sum+sum2;
unsigned __int128 digit = 0;
if(rsum == 0){
struct ListNode* result = malloc(sizeof(struct ListNode));
result->val = rsum;
result->next = NULL;
return result;
}
while (rsum > 0) {
int digit = rsum % 10;
insert_begging(&result, digit);
rsum /= 10;
}
return result;
}
so I spent 1 hour trying to solve this problem, with no luck
this is the test i failed:
l1 = [2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9]
l2 = [5,6,4,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9,9,9,9]
result is supposed to be:
[8,0,7,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,6,4,8,7,2,4,3,8]
firstly I got int overflows even with unsigned long long type so I changed it to unsigned __int128 but i got this:
[1,7,0,4,9,1,2,5,7,9,2,0,1,8,3,3,6,8,2,6,4,9,7,6,4,3,9,5,8,5,1,6,4,5,3,5,7,9,8]
Nobody will help us if we, beginners, will not help each other.:)
It is obvious that neither object of a fundamental integer type can hold such big numbers.
So the approach to build a number in an object of a fundamental integer type does not work.
A straightforward approach can look the following way as shown in the demonstration program below.
An alternative and more efficient approach is at first to build the result list using one of the passed lists in the reversed order and then add the second list and after that again to reverse the result list.
Here is the demonstration program that uses the straightforward approach.
#include <stdio.h>
#include <stdlib.h>
struct ListNode
{
unsigned int digit;
struct ListNode *next;
};
void clear( struct ListNode **head )
{
while (*head)
{
struct ListNode *current = *head;
*head = ( *head )->next;
free( current );
}
}
void assign( struct ListNode **head, const unsigned int a[], size_t n )
{
clear( head );
while (n--)
{
*head = malloc( sizeof( struct ListNode ) );
( *head )->digit = *a++;
( *head )->next = NULL;
head = &( *head )->next;
}
}
FILE * display( const struct ListNode *head, FILE *fp )
{
if (head == NULL)
{
fputc( '0', fp );
}
else
{
for (; head != NULL; head = head->next)
{
fputc( head->digit + '0', fp );
}
}
return fp;
}
struct ListNode * addTwoNumbers( const struct ListNode *head1, const struct ListNode *head2 )
{
const unsigned int Base = 10;
struct ListNode *result = NULL;
unsigned int carry = 0;
const struct ListNode *last1 = NULL, *last2 = NULL;
while ( last1 != head1 && last2 != head2 )
{
const struct ListNode *current1 = head1;
while (current1->next != last1)
{
current1 = current1->next;
}
const struct ListNode *current2 = head2;
while (current2->next != last2)
{
current2 = current2->next;
}
struct ListNode *tmp = malloc( sizeof( struct ListNode ) );
tmp->digit = ( current1->digit + current2->digit + carry ) % Base;
tmp->next = result;
result = tmp;
carry = ( current1->digit + current2->digit + carry ) / Base;
last1 = current1;
last2 = current2;
}
while (last1 != head1)
{
const struct ListNode *current1 = head1;
while (current1->next != last1)
{
current1 = current1->next;
}
struct ListNode *tmp = malloc( sizeof( struct ListNode ) );
tmp->digit = ( current1->digit + carry ) % Base;
tmp->next = result;
result = tmp;
carry = ( current1->digit + carry ) / Base;
last1 = current1;
}
while (last2 != head2)
{
const struct ListNode *current2 = head2;
while (current2->next != last2)
{
current2 = current2->next;
}
struct ListNode *tmp = malloc( sizeof( struct ListNode ) );
tmp->digit = ( current2->digit + carry ) % Base;
tmp->next = result;
result = tmp;
carry = ( current2->digit + carry ) / Base;
last2 = current2;
}
if (carry)
{
struct ListNode *tmp = malloc( sizeof( struct ListNode ) );
tmp->digit = carry;
tmp->next = result;
result = tmp;
}
return result;
}
int main( void )
{
unsigned int a1[] =
{
2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 9
};
const size_t N1 = sizeof( a1 ) / sizeof( *a1 );
unsigned int a2[] =
{
5, 6, 4, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 9, 9, 9, 9
};
const size_t N2 = sizeof( a2 ) / sizeof( *a2 );
struct ListNode *head1 = NULL;
struct ListNode *head2 = NULL;
assign( &head1, a1, N1 );
assign( &head2, a2, N2 );
fputc( '\n', display( head1, stdout ) );
fputc( '\n', display( head2, stdout ) );
struct ListNode *result = addTwoNumbers( head1, head2 );
fputc( '\n', display( result, stdout ) );
clear( &result );
clear( &head2 );
clear( &head1 );
}
The program output is
2432432432432432432432432432432432432432432432432432432432439
5642432432432432432432432432432432432432432432432432432439999
8074864864864864864864864864864864864864864864864864864872438
If for example the first list contains the number
99999999999999999999
and the second list contains the number
1
then the result will be
100000000000000000000
The function addTwoNumbers can be made more readable if to introduce an additional function that will push a new node on the beginning of the list.
For example
struct ListNode * push_front( struct ListNode *head, unsigned int digit )
{
struct ListNode *tmp = malloc( sizeof( struct ListNode ) );
tmp->digit = digit;
tmp->next = head;
return tmp;
}
struct ListNode * addTwoNumbers( const struct ListNode *head1, const struct ListNode *head2 )
{
const unsigned int Base = 10;
struct ListNode *result = NULL;
unsigned int carry = 0;
const struct ListNode *last1 = NULL, *last2 = NULL;
while ( last1 != head1 && last2 != head2 )
{
const struct ListNode *current1 = head1;
while (current1->next != last1)
{
current1 = current1->next;
}
const struct ListNode *current2 = head2;
while (current2->next != last2)
{
current2 = current2->next;
}
result = push_front( result, ( current1->digit + current2->digit + carry ) % Base );
carry = ( current1->digit + current2->digit + carry ) / Base;
last1 = current1;
last2 = current2;
}
while (last1 != head1)
{
const struct ListNode *current1 = head1;
while (current1->next != last1)
{
current1 = current1->next;
}
result = push_front( result, ( current1->digit + carry ) % Base );
carry = ( current1->digit + carry ) / Base;
last1 = current1;
}
while (last2 != head2)
{
const struct ListNode *current2 = head2;
while (current2->next != last2)
{
current2 = current2->next;
}
result = push_front( result, ( current2->digit + carry ) % Base );
carry = ( current2->digit + carry ) / Base;
last2 = current2;
}
if (carry)
{
result = push_front( result, carry );
}
return result;
}