LeetCode 2 Add Two Numbers Elixir solution

LeetCode problem link: 2. Add Two Numbers

LeetCode 2. Add Two Numbers: short description of the solution

This solution recursively processes both linked lists at the same time. For each call, val1 and val2 contain the current node values, or 0 if the corresponding list has already ended.

The current sum is calculated as val1 + val2 + carry. rem(sum, 10) becomes the value of the new node, while div(sum, 10) is passed as the carry to the next recursive call.

next1 and next2 move to the next nodes of the input lists. Each recursive call creates a new ListNode, and its next field is assigned the node returned by the next call.

The recursion ends at add(nil, nil, 0), when both lists are exhausted and there is no carry left.

Time complexity: O(max(n, m))
Space complexity: O(max(n, m)), due to the recursive call stack, because the recursion is not tail-recursive.

LeetCode 2. Add Two Numbers: Elixir solution

defmodule Solution do
  @spec add_two_numbers(l1 :: ListNode.t | nil, l2 :: ListNode.t | nil) :: ListNode.t | nil
  def add_two_numbers(l1, l2) do
    add(l1, l2, 0)
  end

  defp add(nil, nil, 0), do: nil

  defp add(l1, l2, carry) do
    val1 = if l1, do: l1.val, else: 0
    val2 = if l2, do: l2.val, else: 0

    sum = val1 + val2 + carry

    next1 = if l1, do: l1.next, else: nil
    next2 = if l2, do: l2.next, else: nil

    %ListNode{
      val: rem(sum, 10),
      next: add(next1, next2, div(sum, 10))
    }
  end
end