CODEWITHSUNDEEP
cdata-structureslinked-list
Anshuman Kumar
Anshuman Kumar

Reputation: 577

While running my code, I encountered an Address Sanitizer error

This is a question from LeetCode where I basically have to add two numbers using linked lists. I was fairly confident of what I was doing and my code was accepted on their default test case. However, when I hit submit, it doesn't work on any of their test cases.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
 struct ListNode *temp1= l1,*temp2=l2,*temp3=(struct ListNode*)malloc(sizeof(struct ListNode)),*temp4=temp3,*prev;
    temp3->val=0;
 long long int num1=0,num2=0;
 while (temp1!=NULL)
 {
     num1=num1*(long long int )10 + (long long int )temp1->val;
    temp1 = temp1->next;
 }
 while (temp2!=NULL)
 {
     num2=num2*10 + temp2->val;
     temp2 = temp2->next;
 }
 long long int  num3 = num1+num2;
 do
 {

     temp3->val = (long long int )num3%10;
     temp3->next =  (struct ListNode*)malloc(sizeof(struct ListNode));
     prev=temp3;
     temp3 = temp3->next;
     num3/=(long long int )10;
 } while(num3!=0);
  prev->next=NULL;
  return temp4;
}

I applied a brute force approach and just added the two numbers. It gave me the correct value. Then I create a new linked list where I save everu digit and to compensate for the extra element at the end, I save the previous node in each case. In the end, I delete the connection of the last element to the extra one. I run my code and I get the correct output. I expected [7,0,8] and got [7,0,8]

Here is the traceback:

AddressSanitizer: SEGV on unknown address 0x0000000c7616 (pc 0x0000004019db bp 0x7ffff1366900 sp 0x7ffff13668e0 T0)

There really isn't much anywhere regarding the error. Here was the most similar one I could find but I have been using malloc to allocate the memory anyway and using free(prev->next) messes it all up. link

I also wish to clarify that I am not looking for the ideal answer as I don't want to cheat, just find out what I am doing wrong.

Edit

Adding a do-while looping made me clear 14 additional test cases... out of 1563. A new error has come up

Line 17: Char 15: runtime error: signed integer overflow: 399999999 * 10 cannot be represented in type 'int' (solution.c)

Line 17 refers to the num1=num1*10 + temp1->val line; I decided to replace every int with long long int but it doesn't make a difference except for clearing five additional test cases. ( I casted every value to long long int including the constants)

Upvotes: 0

Views: 160

Answers (1)

kiran Biradar
kiran Biradar

Reputation: 12732

I have made the few changes to not dereference prev pointer when num3 is 0.

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
 struct ListNode *temp1= l1,*temp2=l2,*temp3=(struct ListNode*)malloc(sizeof(struct ListNode)),*temp4=temp3;
    temp3->val=0;
    temp3->next=NULL;

 int num1=0,num2=0;
 while (temp1!=NULL)
 {
     num1=num1*10 + temp1->val;
    temp1 = temp1->next;
 }

 while (temp2!=NULL)
 {
     num2=num2*10 + temp2->val;
     temp2 = temp2->next;
 }

 int num3 = num1+num2;
 while(num3!=0)
 {
     temp3->val = num3%10;
     temp3->next =  (struct ListNode*)malloc(sizeof(struct ListNode));
     temp3->next->next = NULL;
     temp3 = temp3->next;
     num3/=10;
 }

  return temp4;
}

Basically I have removed the prev variable instead directly assigning the NULL. Also you have memory leak of size struct ListNode when sum of the numbers is 0. That I let you to figure out and handle.

But your solution will not work if there are more digits represented in the lists which will eventually overflow the integers int num3 = num1+num2;.

Finally the task to is to add the two list in place not to extract the digits out of them and form the integers.

Upvotes: 3

Related Questions