Leetcode 147: “Insertion Sort List” Java Solution

In this Leetcode problem, we are sorting a singly-linked list using the “insertion sort” algorithm:

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

The steps of the insertion sort algorithm:

Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.

At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the…