My output have an extra 0 in it, why is that

Question

So I'm doing practice on leetcode and this is the 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 contain a single digit. Add the two numbers and return it as a linked list.

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

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

And this is my solution:

class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    vector<int> V1;
    vector<int> V2;
    int sum1 = 0;
    int sum2 = 0;
    ListNode *result = new ListNode(0);
    auto l0 = result;
    while(l1) {
        V1.push_back(l1->val);
        l1=l1->next;
    }

    for (auto it1 = V1.rbegin(); it1 != V1.rend(); it1++) {
        sum1 = sum1 * 10 + (*it1);
    }

    while(l2) {
        V2.push_back(l2->val);
        l2=l2->next;
    }

    for (auto it2 = V2.rbegin(); it2 != V2.rend(); it2++) {
        sum2 = sum2 * 10 + (*it2);
    }
    int sum3 = sum1 + sum2;
    while (sum3 !=0) {
        int extract = sum3 % 10;
        l0->next = new ListNode(extract);
        sum3 /= 10;
        l0=l0->next;
    }

    return result;


}
};

And when I ran it, there is always and extra 0 in my output, for example:

Your input [7,2,7] [2,4,2]

Your answer [0,9,6,9]

Expected answer [9,6,9]

I know there is a smarter way to solve this question, but I want to try to solve it in my way first

Answer 1

Its because you are creating the first node with 0. You have two solutions for that:

• Skip the first element at the end of the function (workaround):

  ListNode* aux = result;
  result = result->next;
  delete aux;
  return result;
  

• Not initialize the listnode to zero, use a nullpointer instead:

s

ListNode *result = nullptr;

// More code...

while (sum3 !=0) {
    int extract = sum3 % 10;
    if (l0 == nullptr) {
        result = new ListNode(extract);
        l0 = result;
    }
    else
        l0->next = new ListNode(extract);
    sum3 /= 10;
    l0=l0->next;
}

Ofc, there are better solutions. You could do the sum directly, without using extra vectors/memory.

Answer 2

You are getting an extra zero because you are doing remainder and division operation 1 time extra than required. You have to modify the condition under last while loop.

while (sum3 > 9) {
    int extract = sum3 % 10;
    l0->next = new ListNode(extract);
    sum3 /= 10;
    l0=l0->next;
}