LeetCode-in-All

148. Sort List

Medium

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]

Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]

Output: [-1,0,3,4,5]

Example 3:

Input: head = []

Output: []

Constraints:

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Solution

# Definition for singly-linked list.
#
# defmodule ListNode do
#   @type t :: %__MODULE__{
#           val: integer,
#           next: ListNode.t() | nil
#         }
#   defstruct val: 0, next: nil
# end

defmodule Solution do
  @spec sort_list(head :: ListNode.t | nil) :: ListNode.t | nil
  def sort_list(head) do
    node_to_list(head, [])
    |> Enum.sort(:desc)
    |> list_to_node(nil)
  end

  defp node_to_list(nil, list), do: list
  defp node_to_list(node, list) do
    node_to_list(node.next, [node.val | list])
  end

  defp list_to_node([], node), do: node
  defp list_to_node([x | tail], node) do
    list_to_node(tail, %ListNode{val: x, next: node})
  end
end