Insertion Sort List

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:

1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
3. It repeats until no input elements remain.

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]

Constraints:

• The number of nodes in the list is in the range [1, 5000].
• -5000 <= Node.val <= 5000

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def insertion_sort_list(head):
    dummy_head = ListNode(0)
    dummy_head.next = head
    
    current = head
    while current and current.next:
        if current.val <= current.next.val:
            current = current.next
        else:
            node_to_insert = current.next
            current.next = current.next.next
            
            # Find the right place to insert
            prev = dummy_head
            while prev.next and prev.next.val < node_to_insert.val:
                prev = prev.next
            
            # Insert the node
            node_to_insert.next = prev.next
            prev.next = node_to_insert
            
    return dummy_head.next


# Example usage (for testing):

# Helper function to create a linked list from a list
def create_linked_list(lst):
    if not lst:
        return None
    head = ListNode(lst[0])
    current = head
    for val in lst[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# Helper function to convert a linked list to a list
def linked_list_to_list(head):
    lst = []
    current = head
    while current:
        lst.append(current.val)
        current = current.next
    return lst


# Example 1
head1 = create_linked_list([4, 2, 1, 3])
sorted_head1 = insertion_sort_list(head1)
print(f"Example 1: {linked_list_to_list(sorted_head1)}")

# Example 2
head2 = create_linked_list([-1, 5, 3, 4, 0])
sorted_head2 = insertion_sort_list(head2)
print(f"Example 2: {linked_list_to_list(sorted_head2)}")

# Example 3: Empty list
head3 = create_linked_list([])
sorted_head3 = insertion_sort_list(head3)
print(f"Example 3: {linked_list_to_list(sorted_head3)}")

# Example 4: Single element list
head4 = create_linked_list([7])
sorted_head4 = insertion_sort_list(head4)
print(f"Example 4: {linked_list_to_list(sorted_head4)}")

# Example 5: Already sorted list
head5 = create_linked_list([1, 2, 3, 4, 5])
sorted_head5 = insertion_sort_list(head5)
print(f"Example 5: {linked_list_to_list(sorted_head5)}")

Explanation:

1. Initialization: A dummy_head node is created to simplify insertion at the beginning of the list.
2. Outer Loop: The current pointer iterates through the list.
3. Inner Loop: If current.val is greater than current.next.val, the node current.next is removed and re-inserted into the sorted portion of the list.
4. Insertion: Find the correct position to insert the node by traversing the sorted portion (from dummy_head) and insert it.
5. Return: The sorted list is returned (pointed to by dummy_head.next).

Time Complexity: O(n^2)

• Worst Case: O(n^2) - occurs when the list is in reverse order. For each element, it may require traversing almost the entire sorted portion to find the correct position.
• Best Case: O(n) - occurs when the list is already sorted. The inner loop (insertion) will only run once for each element, confirming its sorted position.
• Average Case: O(n^2) - on average, each element needs to be compared and shifted within the sorted portion.

Space Complexity: O(1)

• The algorithm uses a constant amount of extra space, regardless of the input size. Only a few pointers (dummy_head, current, prev, node_to_insert) are used.

Edge Cases:

• Empty List: The algorithm handles an empty list gracefully because the outer loop condition while current and current.next: will immediately evaluate to false.
• Single Element List: A single-element list is already sorted, so the algorithm will also exit gracefully.
• Already Sorted List: In this case, the if current.val <= current.next.val: condition is always true, so the inner loop never executes, resulting in O(n) time complexity.