1. Question
445. Add Two Numbers II
You are given two non-empty linked 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
2. Solution
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, root): if root is None: return root head = root root = root.next head.next = None while root: tmp = root.next root.next = head head = root root = tmp return head def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ l1 = self.reverseList(l1) l2 = self.reverseList(l2) ins, head_value = divmod(l1.val + l2.val, 10) head = ListNode(head_value) l1 = l1.next l2 = l2.next while l1 and l2: ins, node_value = divmod(l1.val + l2.val + ins, 10) node = ListNode(node_value) node.next = head head = node l1 = l1.next l2 = l2.next while l1: ins, node_value = divmod(l1.val + ins, 10) node = ListNode(node_value) node.next = head head = node l1 = l1.next while l2: ins, node_value = divmod(l2.val + ins, 10) node = ListNode(node_value) node.next = head head = node l2 = l2.next if ins: node = ListNode(1) node.next = head head = node return head
3. Complexity Analysis
Time Complexity : O(N)
Space Complexity: O(1)