Sorting · 154Medium
Insertion Sort List
Given the head of a singly linked list, sort it using INSERTION SORT and return the sorted head. Insertion sort repeatedly removes the next element and inserts it into its correct position in the sorted prefix.
Constraints
- The list holds 1 to 5000 nodes.
- -5000 <= Node.val <= 5000
- INPUT FORMAT
- `head` is a ListNode object, not an array. The arrays in EXAMPLES list the node values in
- order; the test runner links them into real nodes before calling your function.
Examples
insertionSortList(4 -> 2 -> 1 -> 3) -> 1 -> 2 -> 3 -> 4 insertionSortList(-1 -> 5 -> 3 -> 4 -> 0) -> -1 -> 0 -> 3 -> 4 -> 5 insertionSortList(1) -> 1 // single node insertionSortList(1 -> 2 -> 3) -> 1 -> 2 -> 3 // already sorted, best case insertionSortList(3 -> 2 -> 1) -> 1 -> 2 -> 3 // reverse sorted, worst case insertionSortList(2 -> 1 -> 2 -> 0) -> 0 -> 1 -> 2 -> 2 // duplicates are kept
Edge cases
- A single node is already sorted.
- An already-sorted list is the best case, O(n).
Show the target complexity (spoiler)
- Naive
- Copying to an array, sorting, and rebuilding sidesteps the exercise entirely.
- Target
- O(n^2) time, O(1) space — walk the list, and for each node scan the sorted prefix from a dummy head to find its insertion point and relink.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/20-sorting/154-insertion-sort-list.js ./practice c 154