[LeetCode] Add Two Numbers

 

 

Problem

 

 

 

---

 

Solution

 

The base idea is to go through both lists at the same time, add each nodes, and append it to a result linked list.

Make a variable to keep track of the carry for each sum.

When making a result linked list, create two pointers for it. One pointer will always point to the head of the list. Another will go forward through the list as the code add elements to the linked list.

In each iteration in while loop, check if a node is left in both lists. If one list ended before the other, just add 0 and carries to the remaining nodes.

divmod is a useful python built-in function that takes two numbers, and returns a pair of numbers consisting of the quotient and remainder.

 

# Definition for singly-linked list.
# class 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: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry = 0
        root = n = ListNode(0)
        while l1 or l2 or carry:
        	v1 = 0
            v2 = 0
            if l1:
            	v1 = l1.val
                l1 = l1.next
            if l2:
            	v2 = l2.val
                l2 = l2.next
            carry, result = divmod(v1+v2, 10)
            n.next = ListNode(result)
            n = n.next
        return root.next