Leetcode 2. Add Two Number with Python

문제

You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

두개의 연결 리스트가 주어질때 이 두 링크를 숫자로 간주하고 더해서 리턴하시오.

각 자리는 거꾸로 저장되어 있으며 앞부분은 보이지 않는 0이 있다고 가정한다.

예시

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

제한

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

풀이법

두 수를 더할때 중요한점은 carry를 저장해야 한다는 점이다.

carry만 잘 저장한다면 쉽게 풀수 있을것이다.

class Solution(object):
    def reverseLink(self, l):
        head = l
        pre, cur = None, head
        while cur != None:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

    def printNode(self, l):
        while l != None:
            print(l.val, end=' -> ')
            l = l.next
        print()

    def addTwoNumbers(self, l1: ListNode, l2: ListNode):
        ans = None
        carry = 0
        while l1 != None and l2 != None:
            i = l1.val
            j = l2.val
            l1 = l1.next 
            l2 = l2.next
            sum = carry + i + j
            carry = sum // 10
            sum %= 10
            node = ListNode()
            node.val = sum
            node.next = ans
            ans = node

        while l1 != None:
            i = l1.val
            l1 = l1.next 
            sum = carry + i
            carry = sum // 10
            sum %= 10
            node = ListNode()
            node.val = sum
            node.next = ans
            ans = node

        while l2 != None:
            i = l2.val
            l2 = l2.next 
            sum = carry + i
            carry = sum // 10
            sum %= 10
            node = ListNode()
            node.val = sum
            node.next = ans
            ans = node

        if carry != 0:
            node = ListNode()
            node.val = carry
            node.next = ans
            ans = node

        return self.reverseLink(ans)
        

시간복잡도는 O(N) 공간복잡도도 O(N)이다.