All problems

Insertion Sort List

Medium · linked list

You are given the head of a singly linked list of integers. Return the head of a list holding the same values in ascending order, smallest first. Equal values sit next to each other.

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

The nodes you receive are ListNode objects with a val and a next.

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 come before zero, and zero before the positive numbers.

Example 3

Input: head = [2, 2, 1]

Output: [1, 2, 2]

Equal values stay together.

Constraints