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 teh sum as a linked list.

Solution

When we add digits, we need to keep track of the surplus above 10 so that we can carry it onto the next digit summation. Otherwise, the summation is straight forward. Since the head of the linked list is the least significant digit, we can iterate through both linked lists and add the values as well as any amount carried over from the previous digit.

def add_lists(l1, l2, carry=0):
  value = carry

  if(l1 is not None):
    value += l1.value

  if(l2 is not None):
    value += l2.value

  digit = value % 10
  result = Node(digit)

  if(value >= 10):
    carry = 1
  else:
    carry = 0

  if(l1 != None):
    l1 = l1.next

  if(l2 != None):
    l2 = l2.next

  if(l1 != None or l2 != None):
    more = add_lists(l1, l2, carry)

    result.next = more

  return result

This algorithm iterates over both linked lists, so the time complexity is \(O(n)\), where \(n\) is the number of digits in the larger number.