How do you solve Insertion Sort List on LeetCode?

Insertion Sort List (LeetCode #147) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: Insertion sort is efficient for small datasets or nearly sorted lists.

What is the brute force solution for Insertion Sort List?

The brute force approach for Insertion Sort List is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves creating a new sorted linked list and inserting each element from the original list into its correct position in the sorted list. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Insertion Sort List?

Insertion Sort List uses the following concepts: Linked List, Sorting. The recommended patterns to study are: Linked List, Sorting.

What are the interview tips for Insertion Sort List?

Explain your thought process clearly while coding. Discuss time and space complexity as you go along. Practice writing code without an IDE to simulate interview conditions.

What are common mistakes when solving Insertion Sort List?

Not handling edge cases like an empty list or a single node. Confusing the order of insertion while traversing the sorted list.

#147

Insertion Sort List

Medium

Linked ListSortingLinked ListSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal solution still uses the insertion sort concept but avoids creating a new list. Instead, it modifies the original list in place, making it more efficient in terms of space.

⚙️

Algorithm

3 steps

1Step 1: Create a dummy node to help with easier insertion.
2Step 2: Iterate through each node in the original list.
3Step 3: For each node, find the correct position in the sorted part of the list and insert it there.

solution.py20 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def insertionSortList(head):
8    if not head:
9        return head
10    sorted_head = ListNode(0)  # Dummy node
11    current = head
12    while current:
13        next_node = current.next
14        prev = sorted_head
15        while prev.next and prev.next.val < current.val:
16            prev = prev.next
17        current.next = prev.next
18        prev.next = current
19        current = next_node
20    return sorted_head.next

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loop for insertion, but we optimize space usage by modifying the list in place, resulting in O(1) space complexity.

1Insertion sort is efficient for small datasets or nearly sorted lists.
2Using a dummy node simplifies the insertion process.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.