All problems

Sort List

Medium · linked list

You are given the head of a singly linked list of integers. Return the head of the same values arranged in ascending order (smallest first, equal values next to each other).

You may relink the nodes you were given or build new ones, whichever you prefer. An empty list stays empty.

Examples

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]

Negative numbers sort before zero, and zero before the positives.

Example 3

Input: head = []

Output: []

Constraints

• The number of nodes is in the range [0, 2000].
• -10^5 <= Node.val <= 10^5