Add two numbers: LeetCode

Question

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, 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.

I did find the answer to this problem on net but I wanted help with figuring out what is wrong with my code. I also know my code is not the best in regards to optimization but any help is accepted.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
                ListNode *p=l1, *q=l2;
        ListNode *sum= nullptr, *lastdigit= nullptr;
        int num1=0,num2=0;
        while(p!= nullptr)
        {
            int val1= p->val;
            num1=(10*num1)+val1;
            p=p->next;
        }
        cout<<num1<<endl;
        while(q!=nullptr)
        {
            int val2 = q->val;
            num2 =(10*num2)+val2;
            q=q->next;
        }
        cout<<num2<<endl;
        int sum_=num1+num2;
        int r= sum_%10;
            sum= new ListNode(r);
            sum_/=10;
        lastdigit = sum;
        while(sum_!=0)
        {
            int r= sum_%10;
            lastdigit->next= new ListNode(r);
            lastdigit=lastdigit->next;
            sum_/=10;
        }
        return sum;
    }
};

https://leetcode.com/problems/add-two-numbers/

You're not supposed to first convert the lists to integers, then add the integers, then convert the sum to a new list. (Note that there may be up to 100 digits - far too much for any builtin type.) You're supposed to use the digit-by-digit addition algorithm you learned in primary school and build the result list "as you go". — molbdnilo
– molbdnilo, Commented Apr 27, 2021 at 13:53
yeah I found that solution on leetcode but still I want to know what mistake I am making in this code. Why it is not giving proper answer even for small number. — Tanishka
– Tanishka, Commented Apr 27, 2021 at 14:02
You're missing that the lists are stored in reverse, with the least significant digit first - 123 is stored as 3->2->1->null, but you're converting this to 321. (This storage convention makes the expected solution easier to implement). — molbdnilo
– molbdnilo, Commented Apr 27, 2021 at 14:15
@molbdnilo Can you please provide code of what you are saying. — Tanishka
– Tanishka, Commented Apr 27, 2021 at 14:46
No, I won't give you code. You need to traverse both input lists "in sync", and remember to handle the case where one list is shorter than the other. (It's not terribly difficult if you know how to add two numbers on paper.) — molbdnilo
– molbdnilo, Commented Apr 27, 2021 at 14:53

trincot · Accepted Answer · 2021-04-28 18:06:12Z

Your code turns the input linked lists to integers, but that poses two issues:

The input may have linked lists with up to 100 nodes (digits), which exceeds to the range of the integer data type.
Your code treats the first node as the most significant digit, while it should be treated as the least significant digit.

To fix the second issue, change the first loop of your code as follows:

int pow10 = 1;
while (p!= nullptr) {
    int val1 = p->val;
    num1 += val1 * pow10;
    pow10 *= 10;
    p = p->next;
}

...and do the same for the second loop.

Your final loop, where you build the result list from the integer sum, was correct: there you did put the least significant digit in the head node of the result.

The above correction will make your code run correctly for when the input consists of small linked lists, up to 9 nodes.

For really solving the challenge, you cannot use this algorithm, because of the first issue (int cannot represent 100 digits). You should really break down the addition into adding smaller chunks of the list at a time (most will use one node as "chunk"), and keep track of the carry over from one to the next chunk, and at the same time build the result list in chunks.

As you wrote that you already had access to the solution, I will not provide it here. You can get inspiration also from this question on the same challenge, but C#.

Collectives™ on Stack Overflow

Add two numbers: LeetCode

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related