Insertion Sort List - Practice Coding Problems

Insertion Sort List - Problem

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:

Insertion sort iterates, consuming one input element each repetition and growing a sorted output list
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
It repeats until no input elements remain

The algorithm maintains a sorted portion at the beginning and processes remaining elements one by one, inserting each into its correct position within the sorted portion.

Input & Output

Example 1 — Basic Unsorted List

$ Input: head = [4,2,1,3]

› Output: [1,2,3,4]

💡 Note: The insertion sort processes each node: first 4 becomes sorted portion [4], then insert 2 to get [2,4], then insert 1 to get [1,2,4], finally insert 3 to get [1,2,3,4]

Example 2 — Already Sorted

$ Input: head = [1,2,3,4]

› Output: [1,2,3,4]

💡 Note: List is already sorted, so each node gets inserted at the end of the sorted portion, maintaining the same order

Example 3 — Single Node

$ Input: head = [1]

› Output: [1]

💡 Note: Single node is already sorted by definition

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Unsorted linked list [4,2,1,3]

Process

Apply insertion sort by inserting each node at correct position

Output

Sorted linked list [1,2,3,4]

Key Takeaway

🎯 Key Insight: Maintain sorted portion and insert each remaining node at its correct position using pointer manipulation

Asked in

M Microsoft 35 🍎 Apple 28 F Facebook 22 a Amazon 18

The key insight is to use insertion sort's natural property of maintaining a sorted portion and inserting each new element at the correct position. Best approach uses a dummy node to simplify insertion logic. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Insertion Sort	O(n²)	O(1)	For each node, find correct position in sorted portion and insert
Optimized Insertion Sort	O(n²)	O(1)	Use dummy node to simplify edge cases and pointer management

Brute Force Insertion Sort — Algorithm Steps

Start with first node as sorted portion
For each remaining node, scan sorted portion from beginning
Insert node at correct position
Repeat until all nodes processed

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with dummy node and process each node

Find Position

Scan sorted portion to find insertion point

Insert

Place current node at correct position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    
    // Dummy node to simplify insertion
    struct ListNode dummy;
    dummy.val = 0;
    dummy.next = NULL;
    struct ListNode* current = head;
    
    while (current) {
        struct ListNode* nextNode = current->next;
        
        // Find position to insert current node
        struct ListNode* prev = &dummy;
        while (prev->next && prev->next->val < current->val) {
            prev = prev->next;
        }
        
        // Insert current node
        current->next = prev->next;
        prev->next = current;
        
        current = nextNode;
    }
    
    return dummy.next;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) {
        return NULL;
    }
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current = current->next;
        current->val = arr[i];
        current->next = NULL;
    }
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    
    printf("[");
    struct ListNode* current = result;
    int first = 1;
    while (current) {
        if (!first) printf(",");
        printf("%d", current->val);
        first = 0;
        current = current->next;
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we may scan up to n nodes in sorted portion

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few pointer variables, no extra data structures

✓ Linear Space

89.0K Views

Medium Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Insertion Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler