445.Add Two Numbers II

You are given twonon-emptylinked lists representing two non-negative integers. The most significant digit comes first 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.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

Output:7 -> 8 -> 0 -> 7

Method 1 O(n) time, O(1) space.

• Traverse both values linked list and store their sum into an integer variable.
• Create a new node and reversly construct the linked list to represent the new sum number.

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        n1, n2 = 0, 0
        t1, t2 = l1, l2
        while t1:
            n1 = n1*10+t1.val
            t1 = t1.next
        while t2:
            n2 = n2*10+t2.val
            t2 = t2.next
        _sum = n1+n2
        res = ListNode(0)
        while _sum != 0:
            v = _sum % 10
            res.val = v
            next_node = ListNode(None)
            next_node.next = res
            res = next_node
            _sum /= 10
        return res.next if n1+n2 != 0 else res