Insertion Sort a Singly Linked List

You are tasked with implementing the Insertion Sort algorithm to sort a singly linked list. Insertion Sort is a simple sorting algorithm that builds the final sorted list one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has some advantages: it is simple to implement, efficient for small data sets, and it is adaptive. This challenge will test your understanding of linked list manipulation and the Insertion Sort logic.

Problem Description

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

Key Requirements:

• The sorting must be performed in-place if possible, meaning you should modify the existing linked list nodes rather than creating a completely new list. However, if creating new nodes for the sorted portion is a more straightforward implementation of the insertion sort logic for linked lists, that is acceptable.
• The algorithm must adhere to the principles of Insertion Sort.
• The returned list should be a valid singly linked list.

Expected Behavior:

The algorithm should iterate through the original linked list, taking one node at a time and inserting it into its correct position within a growing sorted portion of the list.

Edge Cases to Consider:

• An empty list.
• A list with only one node.
• A list that is already sorted.
• A list sorted in reverse order.

Examples

Example 1:

Input: head = [4,2,1,3]
(Representing a linked list: 4 -> 2 -> 1 -> 3 -> null)

Output: [1,2,3,4]
(Representing a linked list: 1 -> 2 -> 3 -> 4 -> null)

Explanation: The algorithm iterates through the list.

1. 4 is the first element, considered sorted. Sorted: 4. Unsorted: 2 -> 1 -> 3.
2. 2 is taken. It's smaller than 4, so it's inserted before 4. Sorted: 2 -> 4. Unsorted: 1 -> 3.
3. 1 is taken. It's smaller than 2, so it's inserted before 2. Sorted: 1 -> 2 -> 4. Unsorted: 3.
4. 3 is taken. It's larger than 2 but smaller than 4, so it's inserted between 2 and 4. Sorted: 1 -> 2 -> 3 -> 4. Unsorted: null.

Example 2:

Input: head = [-1,5,3,4,0]
(Representing a linked list: -1 -> 5 -> 3 -> 4 -> 0 -> null)

Output: [-1,0,3,4,5]
(Representing a linked list: -1 -> 0 -> 3 -> 4 -> 5 -> null)

Explanation:

1. Sorted: -1. Unsorted: 5 -> 3 -> 4 -> 0.
2. Take 5. Sorted: -1 -> 5. Unsorted: 3 -> 4 -> 0.
3. Take 3. Insert before 5. Sorted: -1 -> 3 -> 5. Unsorted: 4 -> 0.
4. Take 4. Insert before 5. Sorted: -1 -> 3 -> 4 -> 5. Unsorted: 0.
5. Take 0. Insert before 3. Sorted: -1 -> 0 -> 3 -> 4 -> 5. Unsorted: null.

Example 3: (Edge Case: Empty List)

Input: head = []
(Representing an empty linked list: null)

Output: []
(Representing an empty linked list: null)

Explanation: An empty list is already sorted.

Constraints

• The number of nodes in the list is in the range [0, 5000].
• -5000 <= Node.value <= 5000.
• The linked list structure is standard (each node has a value and a next pointer).

Notes

• Consider using a dummy head node for the sorted list. This can simplify the insertion logic, especially for inserting at the beginning of the sorted list.
• When inserting a node, you'll need to manage the next pointers of the preceding nodes correctly.
• Think about how to traverse the original list while simultaneously building the sorted list.

Let me know if you'd like a hint on a specific part of the algorithm or a more detailed explanation of any concept!