2. Add Two Numbers

Medium

Problem:

Add the numbers in a linked list that are stored in reverse order.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807

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

What to learn:

Truth Table of Full Adder

The Sum and the decision for the next carry-over, Carry out, are determined by three inputs: input values A and B, and the previous carry-over, Carry in.

A	B	Carry in	Sum	Carry out
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Solution:

Data type conversion

1. Reverse the given linked lists

2. Convert the linked list to integer.

3. Add the numbers.

4. Convert the sum to a string.

5. Create a new linked list from the sum.

6. Return the result linked list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Reverse
        node1, prev1 = l1, None
        while node1:
            next, node1.next = node1.next, prev1
            prev1, node1 = node1, next
        reverse1 = prev1

        node2, prev2 = l2, None
        while node2:
            next, node2.next = node2.next, prev2
            prev2, node2 = node2, next
        reverse2 = prev2

        # Int to String
        list1 = ""
        while reverse1:
            list1 += str(reverse1.val)
            reverse1 = reverse1.next

        list2 = ""
        while reverse2:
            list2 += str(reverse2.val)
            reverse2 = reverse2.next

        # Add
        str_out = str(int(list1) + int(list2))

        # Reverse result
        node = ListNode()
        head = node
        for i in range(len(str_out)-1, -1, -1):
            # Create a new node for each digit
            head.next = ListNode(int(str_out[i]))
            head = head.next
        
        return node.next

A little different code, but same logic

What to learn from this code?

• How to make a reversed linked list

• How to convert a string list into a string

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
        
        return prev
    
    def toList(self, node: ListNode) -> ListNode:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list
        
    # String to reversed linked list
    def toReversedLinkedList(self, result: str) -> ListNode:
        prev: LinkNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node
        return node
    
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = self.toList(self.reverseList(l1))
        b = self.toList(self.reverseList(l2))
        resultStr = int(''.join(str(e) for e in a)) + int(''.join(str(e) for e in b))
        
        return self.toReversedLinkedList(str(resultStr))

Full Adder

Original adders perform binary operations using logical circuits, but here we can implement it in a manner similar to a full adder of logical circuits using decimal operations.

We will solve it by referring only to the overall structure of the full adder, which takes the remainder as the operation result and raises the quotient in the form of a carry.

1. l1, l2 play the same role as A, B in the figure above, performing operations on the two input values, and if the digits overflow as follows, a carry is set.

2. If the addition result becomes two digits, the quotient is set as a carry to be used in the next operation, and the remainder is taken as the value.

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        root = head = ListNode(0)

        carry = 0
        while l1 or l2 or carry:
            sum = 0
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next
            print(carry, sum)
            carry, val = divmod(sum + carry, 10)
            print(carry, val)

            head.next = ListNode(val)
            head = head.next
        
        return root.next