Leetcode 2. Add Two Numbers

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

Problem about linked list, but we can solve it without related operations.

The first solution is pretty straight forward: get numbers from linked lists and add them up and return it as the linked list.

The second solution is to operate with linked lists.

Solution 1:

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

class Solution:
    # @param {ListNode} l1
    # @param {ListNode} l2
    # @return {ListNode}
    def getString(self, head):
        if not head:
            return '0'
        s = ''
        while head:
            s = str(head.val) + s
            head = head.next
        return s
        
    def addTwoNumbers(self, l1, l2):
        n1, n2 = self.getString(l1), self.getString(l2)
        n = str(int(n1) + int(n2))
        if n == 0:
            return None
        n = n[::-1]
        head = ListNode(int(n[0]))
        p = head
        for i in xrange(1, len(n)):
            tmp = ListNode(int(n[i]))
            p.next = tmp
            p = p.next
        p.next = None
        return head 

Run Time: 188 ms

Solution 2:

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

class Solution:
    # @param {ListNode} l1
    # @param {ListNode} l2
    # @return {ListNode}
    def addTwoNumbers(self, l1, l2):
        dummy, carry = ListNode(0), 0
        p = dummy
        while l1 or l2:   # s for sum, r for result
            s = carry
            if l1:
                s += l1.val
                l1 = l1.next
            if l2:
                s += l2.val
                l2 = l2.next
            r, carry = s % 10, s / 10
            p.next = ListNode(r)
            p = p.next
        if carry:
            p.next = ListNode(1)
        return dummy.next 

Run Time: 188 ms