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:
- The number of nodes in the list is in the range
[0, 5 * 104]. -105 <= Node.val <= 105
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