This notebook was prepared by Donne Martin. Source and license info is on GitHub.
We could solve this with an iterative or a recursive algorithm, both are well suited for this exercise. We'll use a recursive algorithm for practice with recursion. Note this takes an extra space of O(m) where m is the recursion depth.
value
to carry
data
to value
carry
to 1 if value >= 10, else 0
remainder
to value % 10
node
with the remainder
node.next
to a recursive call on the next
nodes, passing in the carry
node
Complexity:
Notes:
%run ../linked_list/linked_list.py
class MyLinkedList(LinkedList):
def _add_reverse(self, first_node, second_node, carry):
# Base case
if first_node is None and second_node is None and not carry:
return None
# Recursive case
value = carry
value += first_node.data if first_node is not None else 0
value += second_node.data if second_node is not None else 0
carry = 1 if value >= 10 else 0
value %= 10
node = Node(value)
node.next = self._add_reverse(
first_node.next if first_node is not None else None,
second_node.next if first_node is not None else None,
carry)
return node
def add_reverse(self, first_list, second_list):
# See constraints
if first_list is None or second_list is None:
return None
head = self._add_reverse(first_list.head, second_list.head, 0)
return MyLinkedList(head)
%%writefile test_add_reverse.py
import unittest
class TestAddReverse(unittest.TestCase):
def test_add_reverse(self):
print('Test: Empty list(s)')
self.assertEqual(MyLinkedList().add_reverse(None, None), None)
self.assertEqual(MyLinkedList().add_reverse(Node(5), None), None)
self.assertEqual(MyLinkedList().add_reverse(None, Node(10)), None)
print('Test: Add values of different lengths')
# Input 1: 6->5->None
# Input 2: 9->8->7
# Result: 5->4->8
first_list = MyLinkedList(Node(6))
first_list.append(5)
second_list = MyLinkedList(Node(9))
second_list.append(8)
second_list.append(7)
result = MyLinkedList().add_reverse(first_list, second_list)
self.assertEqual(result.get_all_data(), [5, 4, 8])
print('Test: Add values of same lengths')
# Input 1: 6->5->4
# Input 2: 9->8->7
# Result: 5->4->2->1
first_head = Node(6)
first_list = MyLinkedList(first_head)
first_list.append(5)
first_list.append(4)
second_head = Node(9)
second_list = MyLinkedList(second_head)
second_list.append(8)
second_list.append(7)
result = MyLinkedList().add_reverse(first_list, second_list)
self.assertEqual(result.get_all_data(), [5, 4, 2, 1])
print('Success: test_add_reverse')
def main():
test = TestAddReverse()
test.test_add_reverse()
if __name__ == '__main__':
main()
Overwriting test_add_reverse.py
%run -i test_add_reverse.py
Test: Empty list(s) Test: Add values of different lengths Test: Add values of same lengths Success: test_add_reverse