2.5 Sum Lists – CCI

  • add two nodes by position
  • if value is greater or equal to 10, take out the carry term
  • get the remaining list by recursively calling the function
  • set the current node to the head of the remaining list
  • return the current node
# [2.5] Sum Lists: You have two numbers represented by a linked
# list, where each node contains a single digit. The digits
# are stored in reverse order, such that the 1's digit is at 
# the head of the list. Write a function that adds the two
# numbers and returns the sum as a linked list.

# Example: (7, 1, 6) + (5, 9, 2) -> (2,1,9)

# Space complexity: O(N)
# Time complexity: O(N)

import unittest

class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def add_lists(node1, node2, carry_received=0):
    if check_if_no_values(node1, node2, carry_received):
        return None

    node_sum = add_nodes(node1, node2, carry_received)
    sum_node_value, carry_pass = split_carry_value(node_sum)
    remaining_list = get_remaining_list(node1, node2, carry_pass)
    current_node = create_node(sum_node_value)
    current_node = set_next_node(current_node, remaining_list)
    
    return current_node

def check_if_no_values(node1, node2, carry):
    if carry == 0:
        if not (node1 or node2):
            return True
    
    return False

def add_nodes(node1, node2, carry):
    if node1 and node2:
        node_sum = node1.value + node2.value + carry
    elif node1 or node2:
        remaining_node = node1 or node2
        node_sum = remaining_node.value + carry
    else:
        node_sum = carry

    return node_sum

def split_carry_value(node_sum):
    if node_sum >= 10:
        carry_pass = 1
        node_sum -= 10
    else:
        carry_pass = 0

    return node_sum, carry_pass
    
def get_remaining_list(node1, node2, carry_pass):
    if node1 and node2:
        remaining_list = add_lists(node1.next, node2.next, carry_pass)
    elif node1:
        remaining_list = add_lists(node1.next, None, carry_pass)
    elif node2:
        remaining_list = add_lists(None, node2.next, carry_pass)
        
    else:
        remaining_list = add_lists(None, None, carry_pass)

    return remaining_list

def create_node(value):
    return Node(value)

def set_next_node(current_node, next_node):
    current_node.next = next_node
    return current_node

class Test(unittest.TestCase):
    
    def test_add_lists(self):
        list1a = Node(7, Node(1, Node(6)))
        list1b = Node(5, Node(9, Node(2)))
        list_sum1 = add_lists(list1a, list1b)
        self.assertEqual(self.node_vals_to_list(list_sum1), [2,1,9])

        list2a = Node(7, Node(1, Node(6)))
        list2b = Node(5, Node(9, Node(4)))
        list_sum2 = add_lists(list2a, list2b)
        self.assertEqual(self.node_vals_to_list(list_sum2), [2,1,1,1])

        list3a = Node(7)
        list3b = Node(3, Node(0, Node(1)))
        list_sum3 = add_lists(list3a, list3b)
        self.assertEqual(self.node_vals_to_list(list_sum3), [0,1,1])

    def node_vals_to_list(self, node):
        result = []
        while node:
            result.append(node.value)
            node = node.next

        return result
        
if __name__ == '__main__':
    unittest.main()