tags: learning leetcode

#2 Add Two numbers

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

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.

I will try: convert them to decimal numbers

• Convert l1 and l2 to numbers.
• Add them up
• Conver the sum to a linked list

---

Try 0

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        
        def ltonum(l1):
            l1ptr = l1
            l1num = 0
            while l1ptr.next != None:
                l1num= l1num * 10 + l1ptr.val
                l1ptr = l1ptr.next
            return l1num
        
        l1num = ltonum(l1)
        l2num = ltonum(l2)
        
        l3num = l1num + l2num
        
        l3 = None
        while l3num != 0:
            l3new = ListNode(l3num % 10)
            l3new.next = l3
            l3num = l3num % 10
            l3 = l3new
        
        return l3
            

try 2 wrong

Finished
Runtime: 8 ms
Your input
[2,4,3]
[5,6,4]
Output
[0]
Expected
[7,0,8]

---

Try 1

class Solution(object):
    def addTwoNumbers(self, l1, l2):

        def ltonum(l1):
            l1ptr = l1
            l1num = 0
            while l1ptr != None:
                l1num= l1num * 10 + l1ptr.val
                l1ptr = l1ptr.next
            return l1num
        l1num = ltonum(l1)
        l2num = ltonum(l2)
        l3num = l1num + l2num
        l3 = None
        while l3num != 0:
            l3new = ListNode(l3num % 10)
            l3new.next = l3
            l3num = (l3num/ 10)
            l3 = l3new
        return l3

try 2 wrong

Your input
[2,4,3]
[5,6,4]
Output
[8,0,7]
Expected
[7,0,8]

---

Try 2

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        def ltonum(l1):
            l1ptr = l1
            l1num = 0
            while l1ptr != None:
                l1num= l1num * 10 + l1ptr.val
                l1ptr = l1ptr.next
            return l1num
        l1num = ltonum(l1)
        l2num = ltonum(l2)
        l3num = l1num + l2num
        l3 = None
        l3old = None
        while l3num != 0:
            l3new = ListNode(l3num % 10)
            if l3old != None:
                l3old.next = l3new
            else:
                l3 = l3new # as the head
            l3num = int(l3num / 10)
            l3old = l3new
        return l3

try 2 wrong

Input
[0]
[0]
Output
[]
Expected
[0]

Wrong Answer

I didn't take care of zeros.

Revision

I will take take of zeros

---

Try 3

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        def ltonum(l1):
            l1ptr = l1
            l1num = 0
            while l1ptr != None:
                l1num= l1num * 10 + l1ptr.val
                l1ptr = l1ptr.next
            return l1num
        l1num = ltonum(l1)
        l2num = ltonum(l2)
        l3num = l1num + l2num
        
        # first node
        l3 = ListNode(l3num % 10) # head
        # remaining nodes, if there are any
        l3num = int(l3num / 10)
        l3tail = l3
        while l3num != 0:
            l3new = ListNode(l3num % 10)
            l3tail.next = l3new
            l3tail = l3new
            l3num = int(l3num / 10)
        return l3

try 3 wrong

Input
[1,8]
[0]
Output
[8,1]
Expected
[1,8]

The Mistake I made

I didn't convert l1 and l2 to numbers correctly, from the very beginning, QQQQ.

try 4

If l1 or l2 is null, it will be mapped to a zero.
I don't need a dummy head for the output, since I will have at least a digit from the sum of l1 and l2.

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        def ltonum(l1): # convert linked list to numbers; a null list leads to a zero
            l1ptr = l1  # current position for l1
            l1num = 0  # initiate the number
            i = 0  # initiate the power of ten
            while l1ptr != None:  # to void usig a null ptr to refer
                l1num += l1ptr.val * pow(10, i)  # starting from least significant digit, multiplying 10^i, `i` is increasing
                l1ptr = l1ptr.next  # shift the current position to the next node
                i += 1
            return l1num
        
        l1num = ltonum(l1)
        l2num = ltonum(l2)
        l3num = l1num + l2num
        
        # first node
        l3 = ListNode(l3num % 10) # head; the least significant digit as the head
        
        # remaining nodes, if there are any
        l3num = int(l3num / 10)  # the next least significant digit
        l3tail = l3  # only one node; the head is also the tail
        while l3num != 0:
            l3new = ListNode(l3num % 10)
            l3tail.next = l3new  # let the current tail point to the new node
            l3tail = l3new  # update the position of the tail
            l3num = int(l3num / 10)  # go to the next digit
        return l3  # return the head

try 4 success

Runtime: 36 ms, faster than 99.97% of Python online submissions for Add Two Numbers.
Memory Usage: 11.8 MB, less than 74.88% of Python online submissions for Add Two Numbers.
Next challenges:
Multiply Strings
Add Binary
Sum of Two Integers
Add Strings
Add Two Numbers II
Add to Array-Form of Integer

---

learn and check

Learn to run code.
This is incorrect.
I made a mistake of reversing the order of linked list

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
def addTwoNumbers(l1, l2):
    def ltonum(l1):
        l1ptr = l1
        l1num = 0
        while l1ptr != None:
            l1num= l1num * 10 + l1ptr.val
            l1ptr = l1ptr.next
        print(l1num)
        return l1num
    
    l1num = ltonum(l1)
    l2num = ltonum(l2)
    l3num = l1num + l2num
    print(l3num)
    
    l3 = None
    l3old = None

    while l3num != 0:
        l3new = ListNode(l3num % 10)
        if l3old != None:
            l3old.next = l3new
        else:
            l3 = l3new # as the head
        l3num = int(l3num / 10)
        l3old = l3new
    return l3
        
l1_2 = ListNode(2)
l1_4 = ListNode(4)
l1_3 = ListNode(3)

l1_2.next = l1_4
l1_4.next = l1_3

l2_5 = ListNode(5)
l2_6 = ListNode(6)
l2_4 = ListNode(4)

l2_5.next = l2_6
l2_6.next = l2_4

l3 = addTwoNumbers(l1_2, l2_5)

while l3 != None:
    print(l3.val)
    l3 = l3.next

243
564
807
7
0
8

Solution of others

Elementary Math

Java

Using a dummy head can avoid accessing a pointer with null address.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

Elementary Math, Recursive Style

Python3

class Solution:
    def addTwoNumbers(self, l1, l2 ,c = 0):

        val = l1.val + l2.val + c
        c = val // 10
        ret = ListNode(val % 10 ) 
        
        if (l1.next != None or l2.next != None or c != 0):
            if l1.next == None:
                l1.next = ListNode(0)
            if l2.next == None:
                l2.next = ListNode(0)
            ret.next = self.addTwoNumbers(l1.next,l2.next,c)
        return ret

Elementary Math, divmod, Dummy Head

class Solution(object):
    def addTwoNumbers(self, l1, l2):
    
        result = ListNode(0)
        result_tail = result
        carry = 0
                
        while l1 or l2 or carry:            
            val1  = (l1.val if l1 else 0)
            val2  = (l2.val if l2 else 0)
            carry, out = divmod(val1+val2 + carry, 10)    
                      
            result_tail.next = ListNode(out)
            result_tail = result_tail.next                      
            
            l1 = (l1.next if l1 else None)
            l2 = (l2.next if l2 else None)
               
        return result.next