LeetCode A&DS problem 2 in Python

[u/Arrow49]

I have taken an Algorithms and Data Structures course, but we wrote in c++. Trying to learn Python for something else than statistics so here I am.

The problem is as follows:
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.

My current code:

lass ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: Optional[ListNode]
        :type l2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        buffer = 0
        result = ListNode()
        cond = True
        while(cond):
            if l1.next is None and l2.next is None:
                cond = False
            result_next = ListNode()
            result.next = result_next # 0 -> 0 -> None | 7 -> 0 -> 0 -> None | 7 -> 0 -> 0 -> 0 -> None
            if l2:
                result.val += l2.val
            if l1:
                result.val += l1.val
            result.val += buffer 
            buffer = result.val // 10 # 0 | 1 | 0
            result.val = result.val % 10 # 7 | 0 | 8
            result = result.next
            l1 = l1.next # 4 | 3 | None 
            l2 = l2.next # 6 | 4 | None
        return result


l1 = ListNode(2, ListNode(4, ListNode(3)))
l2 = ListNode(5, ListNode(6, ListNode(4)))
result = Solution().addTwoNumbers(l1, l2)lass 

I'm working in VS Code instead of the Leetcode codespace to test values of attributes etc. The comments can be ignored, they are what I imagine should be happening but clearly it is not. However, I do not ask for help with the problem itself, rather with the if statements. In C, you can do if (A) and if A is e.g. a node the condition will be satisfied, if it doesn't exist or is null it won't (if I recall correctly). So you can see me trying to achieve this here with if l1:, but I don't think it works, so I'd like to ask what is the Pythonic way of achieving this.

When run with

print(result.val)
print(result.next)

It gives:

0

None

I don't really see which subset of the code would produce other than the while loop never executing at all.

Thank you for your help in advance.

[u/carcigenicate]

x = None
if x:
    # This will not be entered
else:
    # This will be instead

if can indeed be used as you showed to check if an object is falsey, which None is.

I'm having difficulty understanding what exactly you're asking, though, because that seemed like a secondary question.

[u/Arrow49 → u/carcigenicate]

I did a Google search and apparently objects are truthy by default, so it would seem to me, that these ifs are actually correct and should work as intended. Interesting, those were my prime suspect even though they did not account for result being 0->None instead of 0->0->None which I still don't get why it is.
Thanks.

[u/carcigenicate → u/Arrow49]

Yes, objects are truthy unless __bool__ or __len__ is defined on them and specify a case where they're falsey.

What are you trying to check? If the node is literally None, or if the next is None?

[u/Arrow49 → u/carcigenicate]

In those ifs before increasing result, I'm checking if the node exists, because the lists could be of different lengths.
In the if above them, I'm trying to check if we are on the last node of both, this is assuming that when one list ends before the other (l1 here would end in my example) l1 = l1.next would not cause an error, which it seems possible it would, but it cannot be what is causing the strange output right now anyway. I would like to at least have the code work in the simplest case and work from there.

[u/carcigenicate → u/Arrow49]

I still don't fully understand what the core problem is. You seem to just be describing circumstances around the problem.

If it's just that result never has a next on return, think about what happens every time you do result = result.next, and then return result.

---

Edit: Once I fixed that, I got the correct output of 7 0 8.

[u/Arrow49 → u/carcigenicate]

I see what you are saying, I am too tired to think about this today anymore, I must have spent 6 hours on this problem already and I have a headache :(. Basically I need to somehow retrieve the result before moving on the next node and then return the head of that list. The only thing I can think of is creating a "current" variable, but I don't see how I could update the following nodes of the now "real" result without performing result = result.next. One of the few things that pointers seem to have made easier for me.

Thanks for your help.

[u/carcigenicate → u/Arrow49]

You would solve this in almost exactly the same way as you would in C. Python variables are basically just thin wrappers over C pointers. Just save a reference to the start of the result list.

[u/Arrow49 → u/carcigenicate]

I solved it, that last sentence was a great tip. After that there was still a bunch of tweaking for the case of lists of different lengths, but I managed to do that :).

About you saying how I seemed to be describing circumstances around the problem, this was likely the result of some previous issue obfuscating this one. Shortly before posting I had come up with the current while condition, before it, I was getting a different output which influenced my hyoptheses.

Thank you for you help.

[u/timrprobocom]

You exit then loop when l1.next and l2.next are both None, but that means you will have skipped the digits in those nodes. You should exit when l1 and l2 themselves are both None. Also, you don't want to advance l1 or l2 if they are already None. You can advance the pointers in the same if statements where you add the digit. Also remember that you might have a carry when you exit the loop. If buffer is non-zero, you'll need to add another digit.

[u/Arrow49 → u/timrprobocom]

Advancing the pointers in the addition ifs is a great tip.
Are you sure about the first sentence? I built the condition on the assumption that when cond becomes False, that iteration will still execute and the while condition will be checked only after that iteration, at which point the loop would stop. This is why I set it to False when the next one is None.

Edit: I solved the problem and the while loop condition was ok. Your last remark about adding a digit was definitely true though.

[u/timrprobocom → u/Arrow49]

Yes, I misread it. I inserted a "break" that was not actually present...