Sort a singly linked list by inserting each node into its correct position in the already-built sorted prefix.
Problem
Given the head of a singly linked list, reorder the nodes so that the list becomes sorted in non-decreasing order.
Use the insertion sort idea: process nodes one by one and insert each node into its correct position within the portion of the list that has already been sorted.
You must rearrange the existing nodes rather than creating a new list of values.
Notes
- The linked list may contain duplicate values.
- The goal is to sort the list by changing node links.
- A stable ordering is naturally preserved by insertion-sort style insertion when equal values are handled carefully.
Input Format
- The input is the head of a singly linked list.
- Each node contains an integer value.
Output Format
- Return the head of the linked list after it has been sorted in non-decreasing order.
Constraints
- The list length is finite and may be empty.
- Node values can be negative, zero, or positive integers.
- Reuse the existing nodes; do not sort by converting the list into an array of values for the final answer.
Example 1
Input
head = [4,2,1,3]
Output
[1,2,3,4]
Explanation
Insert 2 before 4, then 1 before 2, then 3 between 2 and 4.
Example 2
Input
head = [-1,5,3,4,0]
Output
[-1,0,3,4,5]
Explanation
Each node is inserted into its correct position in the growing sorted list.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.