Log inSign up
mediumLeetCodeNot Started

Insertion Sort List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given the head of a singly linked list, sort the list using insertion sort, and return the *sorted list's head*.

The steps of the insertion sort algorithm: 1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. 2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. 3. It repeats until no input elements remain.

Example 1 · Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]
Explanation: Nodes are sorted into ascending numerical order: 1 -> 2 -> 3 -> 4.

Example 2 · Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Explanation: Negative and non-negative numbers are sorted correctly in ascending order.

Constraints:

  • The number of nodes in the list is in the range [1, 5000].
  • -5000 <= Node.val <= 5000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement in-place pointer insertion without losing reference to unsorted remainder.
  • Master the lastSorted lookahead optimization for adaptive O(N) best-case performance.
  • Utilize sentinel dummy heads to simplify head replacements.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Explicit requirement to implement Insertion Sort on singly linked structures.
  • Online sorting scenario where elements arrive sequentially.
  • Small or nearly-sorted linked list inputs.

Algorithmic Decision Tree:

  • Use dummy sentinel to eliminate special-casing for inserting at the absolute new head.
  • Check curr.val >= lastSorted.val before resetting to dummy to achieve linear O(N) performance on sorted inputs.

Connected Patterns:

Sort List (Merge Sort)Insert into a Sorted Circular Linked List

1. Brute Force — Extract to Array, Sort & Overwrite

Intuition

Read all node values into an array, sort the array, and traverse the list again to overwrite each node's val.

Algorithm

  1. Step 1: Traverse list and push all node values into array vals.
  2. Step 2: Sort vals in ascending order.
  3. Step 3: Traverse list again, setting curr.val = vals[i].
  4. Step 4: Return original head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct ListNode {
8 int val;
9 ListNode *next;
10 ListNode(int x) : val(x), next(nullptr) {}
11};
12
13class Solution {
14public:
15 ListNode* insertionSortList(ListNode* head) {
16 if (!head) return nullptr;
17 vector<int> vals;
18 for (ListNode* curr = head; curr; curr = curr->next) {
19 vals.push_back(curr->val);
20 }
21 sort(vals.begin(), vals.end());
22 int i = 0;
23 for (ListNode* curr = head; curr; curr = curr->next) {
24 curr->val = vals[i++];
25 }
26 return head;
27 }
28};
29
30int main() {
31 ListNode* h = new ListNode(4);
32 h->next = new ListNode(2);
33 h->next->next = new ListNode(1);
34 h->next->next->next = new ListNode(3);
35
36 Solution sol;
37 ListNode* sorted = sol.insertionSortList(h);
38
39 cout << "Brute Force Sorted: ";
40 for (ListNode* c = sorted; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
41 cout << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N log N) — Extracts N values in O(N), sorts array in O(N log N), rewrites values in O(N).
  • Space complexity: O(N) — Allocates array buffer of size N.

Why Brute Force Doesn't Scale:

For reverse-sorted lists of size N, total comparisons equal N*(N-1)/2, which becomes slow for N > 50,000.

For N = 5,000, O(N2) takes ~12.5M operations (~10ms). For general O(N log N) sorting, prefer Merge Sort (sort-list).

2. Better — Unoptimized Pointer Insertion Sort (Reset to Dummy Every Time)

Intuition

Maintain an initially empty sorted list starting with dummy head. Take nodes one by one from the input list and traverse from dummy head to find the first node with a larger value, then splice the node in.

Algorithm

  1. Step 1: Create dummy = new ListNode(0).
  2. Step 2: curr = head.
  3. Step 3: While curr != null:
  4. a. Save nextTemp = curr.next.
  5. b. Set prev = dummy.
  6. c. While prev.next != null && prev.next.val < curr.val, advance prev = prev.next.
  7. d. Splice: curr.next = prev.next, prev.next = curr.
  8. e. Advance curr = nextTemp.
  9. Step 4: Return dummy.next.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* insertionSortList(ListNode* head) {
14 ListNode* dummy = new ListNode(0);
15 ListNode* curr = head;
16
17 while (curr != nullptr) {
18 ListNode* nextTemp = curr->next;
19 ListNode* prev = dummy;
20 while (prev->next != nullptr && prev->next->val < curr->val) {
21 prev = prev->next;
22 }
23 curr->next = prev->next;
24 prev->next = curr;
25 curr = nextTemp;
26 }
27
28 ListNode* result = dummy->next;
29 delete dummy;
30 return result;
31 }
32};
33
34int main() {
35 ListNode* h = new ListNode(4);
36 h->next = new ListNode(2);
37 h->next->next = new ListNode(1);
38 h->next->next->next = new ListNode(3);
39
40 Solution sol;
41 ListNode* sorted = sol.insertionSortList(h);
42
43 cout << "Better Pointer Sorted: ";
44 for (ListNode* c = sorted; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
45 cout << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N^2) — Always scans from the dummy head node to find insertion position for each of the N nodes.
  • Space complexity: O(1) — Operates strictly in-place with O(1) pointers.

3. Optimal — In-Place Insertion Sort with lastSorted Lookahead Fast-Path

Intuition

Maintain dummy, lastSorted = head, and curr = lastSorted.next. If lastSorted.val <= curr.val, curr is already in the correct position; simply advance lastSorted = lastSorted.next. If not, search from dummy to find prev, splice curr in front of prev.next, and connect lastSorted.next = curr.next.

Algorithm

  1. Step 1: If head == null || head.next == null, return head.
  2. Step 2: Create dummy = new ListNode(0, head), lastSorted = head, curr = head.next.
  3. Step 3: While curr != null:
  4. a. If lastSorted.val <= curr.val: advance lastSorted = lastSorted.next.
  5. b. Else: find prev = dummy; while prev.next.val < curr.val, advance prev = prev.next. Splice lastSorted.next = curr.next, curr.next = prev.next, prev.next = curr.
  6. c. Update curr = lastSorted.next.
  7. Step 4: Return dummy.next.

Insertion Sort List Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Prefix is now [2, 4]
Visual state
Values and pointers at this exact step
linked list
lastSorted → 4
Node 2
2
Node 4
4
Node 1
1
Node 3
3
NULL
Check / comparison
2 < 4
Decision / next transition
Insert at head
Why this step matters

Prefix is now [2, 4].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode *n) : val(x), next(n) {}
10};
11
12class Solution {
13public:
14 ListNode* insertionSortList(ListNode* head) {
15 if (!head || !head->next) return head;
16
17 ListNode* dummy = new ListNode(0, head);
18 ListNode* lastSorted = head;
19 ListNode* curr = head->next;
20
21 while (curr != nullptr) {
22 if (lastSorted->val <= curr->val) {
23 lastSorted = lastSorted->next;
24 } else {
25 ListNode* prev = dummy;
26 while (prev->next->val < curr->val) {
27 prev = prev->next;
28 }
29 lastSorted->next = curr->next;
30 curr->next = prev->next;
31 prev->next = curr;
32 }
33 curr = lastSorted->next;
34 }
35
36 ListNode* result = dummy->next;
37 delete dummy;
38 return result;
39 }
40};
41
42int main() {
43 ListNode* h = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
44
45 Solution sol;
46 ListNode* sorted = sol.insertionSortList(h);
47
48 cout << "Optimal In-Place Sorted: ";
49 for (ListNode* c = sorted; c; c = c->next) {
50 cout << c->val << (c->next ? " -> " : "");
51 }
52 cout << endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(N^2) worst case, O(N) best case — If input is sorted or partially sorted, elements in order take O(1) without head traversal. Worst case (reverse sorted) is O(N2).
  • Space complexity: O(1) — Operates strictly in-place with O(1) auxiliary pointers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Copy to Array, Sort, and ReassignO(N log N)O(N)Extract all node values into an array, sort the array using language built-in sort, then write values back into the linked list nodes.Memory allocation and cheating the pointer sorting requirement.
2.Better — Naive Linked List Insertion SortO(N^2)O(1)For every node, always start searching from the dummy head to find its insertion position, regardless of whether it is already larger than the previous sorted element.Always resetting search to dummy head on every node.
3.Optimal — Optimized Insertion Sort with lastSorted Fast-PathOptimalO(N^2) worst case, O(N) best caseO(1)Maintain lastSorted and curr = lastSorted.next. If lastSorted.val <= curr.val, advance lastSorted = curr in O(1). Otherwise, search from dummy to prev, splice curr, and resume without resetting lastSorted position.Optimal for insertion sort algorithm.

Common Pitfalls & Crucial Edge Cases

Losing the rest of the list

Forgetting lastSorted.next = curr.next before redirecting curr.next severs the unsorted tail.

Resetting search pointer incorrectly

Failing to update curr = lastSorted.next after splicing.

Not using a dummy head

Inserting before the minimum element without a sentinel requires clunky special cases for reassigning head.

Crucial Edge Cases to Validate:

  • Single Element List — head = [1] -> returned immediately in O(1).
  • Already Sorted List — head = [1, 2, 3, 4, 5] -> executes in strict O(N) linear time thanks to lastSorted.val <= curr.val check.
  • Reverse Sorted List — head = [5, 4, 3, 2, 1] -> every node is moved to the dummy head position (O(N2) comparisons).
  • Duplicate Values — head = [3, 1, 3, 2] -> stable sorting preserves relative order.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the lastSorted lookahead trick immediately: 'We can make insertion sort adaptive (O(N) best case) by comparing curr with lastSorted first.'
  2. State why Merge Sort is usually preferred for large linked lists, but Insertion Sort is optimal for small or nearly sorted lists with zero memory overhead.
  3. Use a dummy head sentinel to eliminate head-insertion edge cases.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the best-case time complexity of the optimized insertion sort on a linked list?

2.Why is insertion sort on a linked list different from insertion sort on an array?

3.What role does lastSorted play during pointer manipulation?

Back to DSA Sheet