Insertion Sort List

Medium

Amazon

1 view

Topics:

Linked Lists

You are given the head of a singly linked list. Your task is to sort the list using the insertion sort algorithm and return the head of the sorted linked list. Insertion sort should be performed in-place on the linked list.

Here's how the insertion sort algorithm works:

Iterate through the list, consuming one element at a time.
For each element, find the correct position within the already sorted portion of the list.
Insert the element into that position.
Repeat until all elements have been inserted into the sorted portion.

For example:

Input: 4 -> 2 -> 1 -> 3 Output: 1 -> 2 -> 3 -> 4

Input: -1 -> 5 -> 3 -> 4 -> 0 Output: -1 -> 0 -> 3 -> 4 -> 5

Can you implement this in Java? Also, analyze the time and space complexity of your solution. Consider and discuss any edge cases in your implementation. Finally, explain how your solution is superior (or not) to a naive approach of first converting the LinkedList to an array, sorting the array, and then rebuilding the sorted LinkedList.

Insertion Sort List

Medium

Amazon

1 view

Topics:

Linked Lists

You are given the head of a singly linked list. Your task is to sort the list using the insertion sort algorithm and return the head of the sorted linked list. Insertion sort should be performed in-place on the linked list.

Here's how the insertion sort algorithm works:

Iterate through the list, consuming one element at a time.
For each element, find the correct position within the already sorted portion of the list.
Insert the element into that position.
Repeat until all elements have been inserted into the sorted portion.

For example:

Input: 4 -> 2 -> 1 -> 3 Output: 1 -> 2 -> 3 -> 4

Input: -1 -> 5 -> 3 -> 4 -> 0 Output: -1 -> 0 -> 3 -> 4 -> 5

Can you implement this in Java? Also, analyze the time and space complexity of your solution. Consider and discuss any edge cases in your implementation. Finally, explain how your solution is superior (or not) to a naive approach of first converting the LinkedList to an array, sorting the array, and then rebuilding the sorted LinkedList.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list contain duplicate values?
What is the range of values for the nodes in the linked list?
Can the input linked list be empty or null?
Should I create a completely new list, or can I modify the existing list in place?
What should I return if the input is null?

Brute Force Solution

Approach

The brute force approach for sorting a linked list using insertion sort is similar to how you might sort a hand of playing cards. We'll build a new sorted list, one card (node) at a time, by finding the right spot for each card from the original unsorted list.

Here's how the algorithm would work step-by-step:

Start with an empty new list that will eventually hold all the sorted elements.
Take the first element from the original list.
Walk through the new sorted list from the beginning.
Find the correct position where the element from the original list should be inserted so the new list remains sorted.
Insert the element at that position, shifting the other elements in the sorted list as needed to make space.
Take the next element from the original list and repeat steps 3 through 5.
Continue doing this until all the elements from the original list have been inserted into the new sorted list.
The new list now contains all elements from the original list in sorted order.

Code Implementation

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

def insertionSortList(head):
    sorted_list_head = None

    current_node = head

    while current_node:
        next_node = current_node.next
        
        # Special case for inserting at the beginning
        if not sorted_list_head or current_node.val < sorted_list_head.val:
            current_node.next = sorted_list_head
            sorted_list_head = current_node

        else:
            search_node = sorted_list_head

            # Find the correct position to insert the current node
            while search_node.next and current_node.val > search_node.next.val:
                search_node = search_node.next

            # Insert the current node in the sorted list
            current_node.next = search_node.next
            search_node.next = current_node

        current_node = next_node

    return sorted_list_head

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the original linked list of n elements. For each element, it traverses the sorted portion of the new list to find the correct insertion point. In the worst case (e.g., reverse sorted input), this traversal may require comparing the current element with all elements already in the sorted list, resulting in up to n comparisons. Therefore, inserting each of the n elements may require up to n comparisons, leading to a time complexity of approximately n * n or n². This simplifies to O(n²).

Space Complexity

O(1) – The algorithm constructs a new sorted linked list by iteratively inserting nodes from the original list. The plain English description doesn't indicate any extra data structures are used beyond the nodes being rearranged. It utilizes a constant number of pointers to traverse and manipulate the list structure. Therefore, the auxiliary space required remains constant irrespective of the number of nodes N in the input list, leading to a space complexity of O(1).

Optimal Solution

Approach

We will construct the sorted list one element at a time, similar to how you might sort cards in your hand. We go through the original list, and for each element, we find the correct place to insert it into the already-sorted portion of the new list.

Here's how the algorithm would work step-by-step:

Create a new, empty sorted list to begin with. This will be built up gradually.
Go through each element of the original unsorted list, one at a time.
For each element, walk through the new sorted list from the beginning until you find the place where the element should be inserted to keep everything in order.
Insert the element from the original list into its correct spot in the new sorted list.
Repeat steps 2-4 until every element from the original list has been placed into the new, sorted list.
The new sorted list is now complete.

Code Implementation

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

def insertionSortList(head):
    if not head:
        return None

    sorted_list_head = None

    current_node = head
    while current_node:
        next_node = current_node.next

        # Insert current_node into the sorted list
        if not sorted_list_head:
            sorted_list_head = current_node
            sorted_list_head.next = None
        else:
            # Find the correct position to insert.
            insertion_point_predecessor = None
            insertion_point = sorted_list_head
            while insertion_point and current_node.val > insertion_point.val:
                insertion_point_predecessor = insertion_point
                insertion_point = insertion_point.next

            # Insert at the beginning of the list
            if not insertion_point_predecessor:
                current_node.next = sorted_list_head
                sorted_list_head = current_node
            else:
                # Insert in the middle or end
                current_node.next = insertion_point
                insertion_point_predecessor.next = current_node

        current_node = next_node

    # Return the head of the sorted list.
    return sorted_list_head

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n nodes in the linked list. For each node, it traverses the sorted portion of the list to find the correct insertion point. In the worst-case scenario, where the list is in reverse order, each node will require traversing nearly the entire sorted portion, resulting in approximately n comparisons for each of the n nodes. Thus, the total number of operations approximates n * n/2, which simplifies to O(n²).

Space Complexity

O(1) – The algorithm constructs a new sorted list by inserting elements one by one from the original list. Although a new sorted list is being built, this is ultimately overwriting the original list; the plain English explanation does not refer to using extra space to create a *copy* of the input list. The insertion process itself involves finding the correct position and inserting the node. This operation is done in-place by manipulating pointers. Therefore, no auxiliary data structures that scale with the input size N (the number of elements in the list) are used. The space complexity is thus constant.

Edge Cases

Case	How to Handle
Empty list	Return the head (null) immediately, as there's nothing to sort.
List with only one element	Return the head directly, as a single-element list is already sorted.
List already sorted	The algorithm should still function correctly, though it won't perform any actual swaps, resulting in O(n) complexity in this best-case scenario.
List sorted in reverse order	This represents the worst-case scenario for insertion sort, leading to O(n^2) complexity as each element needs to be moved to the beginning.
List with duplicate values	The algorithm should correctly handle duplicate values by inserting them in their appropriate sorted positions relative to the existing duplicates.
List with negative numbers	The algorithm should correctly handle negative numbers by inserting them in their appropriate sorted positions.
List with very large or very small numbers (close to integer limits)	The algorithm relies on comparisons, so ensure that the comparison operations do not cause integer overflow, potentially by using appropriate data types.
Memory constraints with extremely large lists	Insertion sort is in-place, so memory usage is relatively low, but extremely large lists could still strain memory, potentially requiring consideration of external sorting algorithms in real-world scenarios.