reorder_lists.exs

defmodule ListNode do
  @moduledoc """
  Define a Node type for our linked list.
  """
  @enforce_keys [:data, :next]
  defstruct data: 0,
            next: nil
end

defimpl String.Chars, for: ListNode do
  @moduledoc """
  This enables pretty printing for our Node type.
  """
  def to_string(node) do
    build_string(node)
  end

  defp build_string(%ListNode{data: data, next: nil}) do
    "#{data}"
  end

  defp build_string(%ListNode{data: data, next: next}) do
    "#{data}->#{build_string(next)}"
  end
end

defmodule LinkedList do
  alias ListNode

  # This function does solves the problem at a high level
  def reorder(list) do
    # Find out how big the first half should be
    n = list |> count() |> Kernel.+(1) |> div(2)

    # Get the first half
    first = take(list, n)

    # Get the second half, then reverse it
    second = list |> drop(n) |> reverse()

    # Interleave the two lists
    interleave(first, second)
  end

  def new([data]) do
    %ListNode{data: data, next: nil}
  end

  def new([data | rest]) do
    %ListNode{data: data, next: new(rest)}
  end

  def new(enumerable) do
    enumerable |> Enum.to_list() |> new()
  end

  def count(%ListNode{next: nil}), do: 1

  def count(%ListNode{next: next}) do
    1 + count(next)
  end

  def drop(%ListNode{next: next} = node, amount) when is_nil(next) or amount == 0 do
    node
  end

  def drop(%ListNode{next: next}, amount) do
    drop(next, amount - 1)
  end

  def interleave(first, nil) do
    %{first | next: nil}
  end

  def interleave(%ListNode{next: nil} = first, second) do
    %{first | next: second}
  end

  def interleave(%ListNode{next: next1} = first, %ListNode{next: next2} = second) do
    %{first | next: %{second | next: interleave(next1, next2)}}
  end

  def reverse(node) do
    reverse(node, nil)
  end

  def reverse(%ListNode{next: nil} = current, previous) do
    %{current | next: previous}
  end

  def reverse(%ListNode{next: next} = current, previous) do
    reverse(next, %{current | next: previous})
  end

  def take(%ListNode{next: next}, amount) when is_nil(next) or amount == 0 do
    nil
  end

  def take(%ListNode{next: next} = node, amount) do
    %{node | next: take(next, amount - 1)}
  end
end

list = LinkedList.new(1..4)

IO.puts("#{list} becomes #{LinkedList.reorder(list)}")

list = LinkedList.new(1..5)

IO.puts("#{list} becomes #{LinkedList.reorder(list)}")