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/

Answer 1

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

1. The input may have linked lists with up to 100 nodes (digits), which exceeds to the range of the integer data type.
2. 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#.