Medium
Quiz
#147 Insertion Sort List
APPROACH
Given the head of a singly linked list, sort it using insertion sort and return the sorted list's head.
The insertion sort algorithm:
- Build a sorted output list one element at a time by consuming the input.
- For each new element, find its correct position in the sorted portion and insert it there.
- Repeat until all input elements have been placed.
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]
1 of 4
1:00
What is the optimal approach for this problem?