Insertion Sort List

Medium · Linked Lists · about 15 minutes

Asked at Microsoft, Amazon, Google, Meta.

Sort a linked list the way insertion sort works: build up a sorted list by removing input nodes one at a time and linking each into its proper position in the sorted part. Return the sorted list's head.