Insertion Sort List
Medium · Arrays & Hashing · Linked List · Sorting
Problem
You are given the head of a singly linked list. Sort the list in increasing order using insertion sort, and return the head of the sorted list.
Insertion sort builds the sorted list one node at a time: take the next node from the unsorted part, walk the sorted part to find where it belongs, and splice it in there. Repeat until no unsorted nodes remain.
Lists are shown as arrays of node values, from the head.
Examples
Input: head = [3,-2,8,1] Output: [-2,1,3,8]
Sorted part after each step: [3], [-2,3], [-2,3,8], [-2,1,3,8].
Input: head = [6,6,2] Output: [2,6,6]
2 is spliced in before both 6s.
Input: head = [0] Output: [0]
A single node is already sorted.
Constraints
- 1 <= number of nodes <= 5000
- -5000 <= Node.val <= 5000
Approaches
- Insertion sort, always scanning from the front — time O(n²), space O(1)
Follow-up
Insertion sort is O(n²) on a reversed list. To sort a linked list in O(n log n), use merge sort: split at the middle with slow and fast pointers, sort both halves, and merge them by relinking nodes, which needs no extra array.
Related problems
Start free on Cariara · Coding problems · System design studio
