Linked List

445. Add Two Numbers II

Difficulty: Medium

You are given two linked lists representing two non-negative numbers. 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

Hide Company Tags Microsoft Bloomberg

思路：其实也很直接，就是把list转换成array，然后按照array做再转换回去。时间复杂度不高但是空间很高。可以提高一下。也有人转换成数字做的，一个意思。

# 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
        """
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next

        carry = 0
        res = []
        while s1 or s2 or carry:
            a1 = s1.pop() if s1 else 0
            a2 = s2.pop() if s2 else 0
            total = a1 + a2 + carry
            carry, ans = divmod(total, 10)
            res.append(ans)
        head = ListNode(-1)
        move = head
        while res:
            move.next = ListNode(res.pop())
            move = move.next
        return head.next