0
#include <iostream>
 //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 *final_ll;
        ListNode **ptr_final = &final_ll;
        int carry, sum;
        while (l1!=NULL || l2!=NULL || carry > 0)
        {
            int s1 = ((l1!=NULL) ? l1->val: 0);
            int s2 = ((l2!=NULL) ? l2->val: 0);
            sum = s1 + s2 + carry;
            carry = sum / 10;
            (*ptr_final) = new ListNode(sum % 10);
            //std::cout << "tenth_digit = " << carry << std::endl;
            std::cout << "unit_digit = " << sum % 10 << std::endl;
            if (l1!=NULL) l1 = l1->next;
            if (l2!=NULL) l2 = l2->next;
            ptr_final = &((*ptr_final)->next);
        }
        return final_ll;
    }
};
int main() {
    ListNode l1(9);
    ListNode l2(8, &l1);
    ListNode *result = Solution().addTwoNumbers(&l1, &l2);
}

This code outputs:

unit_digit = 5
unit_digit = 1
unit_digit = 1

However, when I uncomment

std::cout << "tenth_digit = " << carry << std::endl;

In Solution class, outputs are changed to:

tenth_digit = 3278
unit_digit = 4
tenth_digit = 328
unit_digit = 7
tenth_digit = 32
unit_digit = 8
tenth_digit = 3
unit_digit = 2
tenth_digit = 0
unit_digit = 3

A single printing statement should not change the number of iterations of the while loop and the value of unit_digit during each iteration. What's happening here?

Acorn
  • 24,970
  • 5
  • 40
  • 69
Guolun Li
  • 77
  • 1
  • 6
  • Ah, the glories of [Undefined Behaviour](https://en.cppreference.com/w/cpp/language/ub). You change a totally unrelated line of code and the program breaks. It's Tuesday the third of September, so the code breaks.You forget your niece's birthday, so the code breaks. I really hate UB. – user4581301 Aug 17 '20 at 04:10
  • Side note: this looks like code for an automated grader or online judge. If you are permitted by the assignment requirements, use [`std::forward_list`](https://en.cppreference.com/w/cpp/container/forward_list) instead of rolling your own singly linked list. Stand on the shoulders of giants when possible. They don't mind. – user4581301 Aug 17 '20 at 04:14
  • @user4581301 Thanks a lot. I'll go over those undefined behaviors to avoid future bugs; this is actually a leetcode question and the usage of `ListNode` Class is required. – Guolun Li Aug 17 '20 at 20:18

1 Answers1

2

Your code has undefined behavior.

In addTwoNumbers(), the final_ll and carry variables are both uninitialized, and both are being used before they have been assigned valid values.

carry holds a random value when declared, throwing off your while loop if that value is not 0.

If l1 and l2 were nullptr, and carry happened to be randomly <= 0, the body of the while loop would not be entered at all, causing addTwoNumbers() to return an indeterminate ListNode* value to the caller. And if carry were randomly > 0 instead, your while loop would run more times than you intend, skewing the results.

You need to initialize both variables, eg:

ListNode *final_ll = nullptr;
...
int carry = 0;

I would also suggest moving the declaration of sum inside the loop, since its value does not need to be preserved across loop iterations:

int carry = 0;
while (l1 || l2 || carry > 0)
{
    ...
    int sum = s1 + s2 + carry;
    ...
}
Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
  • Thank you very much. I have some questions: 1) In `int sum = s1 + s2 + carry;`, Why can you redefine `sum` in each iteration? 2) In `(*ptr_final) = new ListNode(sum % 10);`, when does this temporary pointer get deleted after its initialization? – Guolun Li Aug 17 '20 at 19:43
  • 1) because it is a local variable, defined inside the `{}` brackets of the loop body, and so it will go out of scope at the end of each iteration when `}` is reached. 2) when the caller of `addTwoNumbers()` deletes the nodes of the returned list. – Remy Lebeau Aug 17 '20 at 19:48
  • Sorry for 2) my actual question is why didn't the program give memory leak errors when I don't explicitly `delete ...` pointers on the heap? I was reading this post https://stackoverflow.com/questions/31244269/what-happens-if-i-forget-to-deallocate-memory-in-c . Will the program automatically deallocate memory on the heap, and if so, when? – Guolun Li Aug 17 '20 at 20:14
  • 1
    A modern Operating System will clean up the leaked memory when the program exits. Don't expect a warning or error over a leak, though, because the tracking necessary to trap and report on the leak is expensive and C++ has a policy of not making a program pay for anything they didn't ask for. You typically have to use tools like [AddressSanitizer](https://en.wikipedia.org/wiki/AddressSanitizer) or [Valgrind](https://en.wikipedia.org/wiki/Valgrind) to trace memory mistakes like leaks. – user4581301 Aug 17 '20 at 20:24
  • Thank you guys so much! – Guolun Li Aug 17 '20 at 23:18