Insertion Sort List solution and explanation
Google
9 more videos on this problem
Insertion Sort List - Leetcode 147 - PythonNeetCode · 14:21 · 43K views
Insertion Sort List 🔥| Leetcode 147 | Linked ListAyushi Sharma · 15:22 · 22K views
insertion sort list | leetcode 147 | linked list sortingNaresh Gupta · 5:56 · 20K views
Insertion Sort List | LeetCode 147 | C++, Java, PythonKnowledge Center · 15:10 · 19K views
Insertion Sort List | Live Coding with Explanation | Leetcode #147Algorithms Made Easy · 6:16 · 12K views
Insertion Sort List | Leet code 147 | Theory explained + Python codeSai Anish Malla · 11:32 · 3K views
Insertion Sort List | Leetcode 147 | Live coding session 🔥🔥🔥Coding Decoded · 8:33 · 1K views
Leetcode | 147. Insertion Sort List | Medium | Java SolutionDeveloper Docs · 13:33 · 802 views
Leetcode 147 | Insertion Sort Linked List | JavaTea and Code · 11:52 · 770 views
147 - Insertion Sort List - LeetCode (Medium) | Linked Lists | Insertion Sort O(N^2) ApproachThe Lame Coder · 17:38 · 734 views
The 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 following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.
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]
Constraints:
- The number of nodes in the list is in the range
[1, 5000]. -5000 <= Node.val <= 5000
Approach overview
Problem Overview: You are given the head of a singly linked list and need to sort it using the insertion sort algorithm. Instead of sorting an array, the algorithm must rearrange nodes in a linked list. Each node should be inserted into its correct position in the sorted portion of the list as you iterate through the original list.
Approach 1: Direct Insertion into New List (Time: O(n^2), Space: O(1))
Create a new sorted list and insert nodes from the original list one by one into their correct position. Use a dummy head to simplify edge cases like inserting at the beginning. For every node you take from the input list, iterate through the sorted list until you find the first node with a larger value, then splice the current node before it. Because each insertion may scan up to the entire sorted portion, the total runtime becomes O(n^2). No extra data structures are required besides pointers, so the space complexity stays O(1).
This approach mirrors the textbook insertion sort process: maintain a sorted region and grow it one element at a time. The linked list structure actually makes insertion cheap because pointer updates replace expensive array shifts. The cost comes from repeatedly scanning the sorted list to find the correct insertion point.
Approach 2: In-place Insertion in the List (Time: O(n^2), Space: O(1))
Instead of building a separate list, maintain a sorted prefix within the same list and reposition nodes that are out of order. Track the last node of the sorted portion and compare it with the next node. If the next value is larger, the prefix is still sorted and you move forward. If it is smaller, remove that node and reinsert it from the start using a dummy head pointer.
This technique avoids restarting from scratch each time the list is already partially sorted. Only misplaced nodes trigger a search from the beginning. In many practical inputs this reduces unnecessary scans, though the worst case still reaches O(n^2). Like the previous method, only pointer manipulations are used, keeping the extra space at O(1).
The problem is primarily about pointer control in a linked list while implementing a classic sorting technique. The tricky parts are handling insertion at the head and making sure node references are not lost during re-linking.
Recommended for interviews: The in-place insertion approach is typically what interviewers expect. It demonstrates that you understand insertion sort mechanics and can manipulate linked list pointers safely. The direct insertion method is easier to reason about and is a good starting point, but the in-place version shows stronger control over list operations.
Approach 1: Approach 1: Direct Insertion into New List
This approach involves creating a new sorted list and inserting each element from the original list into the correct position in the new list, maintaining the sorted order.
class ListNode:
def __init__(self, x=0, next=None):
self.val = x
self.next = next
def insertionSortList(head):
if not head:
return None
sorted_head = ListNode(0) # Dummy node
while head:
current = head
head = head.next
prev = sorted_head
while prev.next and prev.next.val < current.val:
prev = prev.next
current.next = prev.next
prev.next = current
return sorted_head.nextclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null) return null;
ListNode sortedHead = new ListNode(0); // Create a dummy node
while (head != null) {
ListNode current = head;
head = head.next;
ListNode prev = sortedHead;
while (prev.next != null && prev.next.val < current.val) {
prev = prev.next;
}
current.next = prev.next;
prev.next = current;
}
return sortedHead.next;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* insertionSortList(ListNode* head) {
if (!head) return NULL;
ListNode* sortedHead = NULL;
while (head) {
ListNode* current = head;
head = head->next;
if (!sortedHead || sortedHead->val >= current->val) {
current->next = sortedHead;
sortedHead = current;
} else {
ListNode* ptr = sortedHead;
while (ptr->next && ptr->next->val < current->val) {
ptr = ptr->next;
}
current->next = ptr->next;
ptr->next = current;
}
}
return sortedHead;
}class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function insertionSortList(head) {
if (!head) return null;
let sortedHead = new ListNode(0); // Dummy node
while (head) {
let current = head;
head = head.next;
let prev = sortedHead;
while (prev.next && prev.next.val < current.val) {
prev = prev.next;
}
current.next = prev.next;
prev.next = current;
}
return sortedHead.next;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* insertionSortList(struct ListNode* head) {
if (head == NULL) return NULL;
struct ListNode* sortedHead = NULL;
while (head) {
struct ListNode* current = head;
head = head->next;
if (sortedHead == NULL || sortedHead->val >= current->val) {
current->next = sortedHead;
sortedHead = current;
} else {
struct ListNode* ptr = sortedHead;
while (ptr->next && ptr->next->val < current->val) {
ptr = ptr->next;
}
current->next = ptr->next;
ptr->next = current;
}
}
return sortedHead;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode InsertionSortList(ListNode head) {
if (head == null) return null;
ListNode sortedHead = new ListNode(0); // Dummy node
while (head != null) {
ListNode current = head;
head = head.next;
ListNode prev = sortedHead;
while (prev.next != null && prev.next.val < current.val) {
prev = prev.next;
}
current.next = prev.next;
prev.next = current;
}
return sortedHead.next;
}
}This Python implementation takes an iterative approach using a dummy node strategy. It extracts each node from the initial list, navigates through the sorted segment, and inserts it into the appropriate slot.
Time Complexity: O(n2), indicated by nested loops for node placements.
Space Complexity: O(1), no additional complex data structures.
Approach 2: Approach 2: In-place Insertion in the List
Instead of creating a new list, this approach involves sorting the nodes within the existing linked list, rearranging the pointers directly.
class ListNode:
def __init__(self, x=0, next=None):
self.val = x
self.next = next
def insertionSortList(head):
if head is None or head.next is None:
return head
sorted_head = head
head = head.next
sorted_head.next = None
while head:
current = head
head = head.next
if current.val <= sorted_head.val:
current.next = sorted_head
sorted_head = current
else:
ptr = sorted_head
while ptr.next and ptr.next.val < current.val:
ptr = ptr.next
current.next = ptr.next
ptr.next = current
return sorted_headclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode sorted = head;
head = head.next;
sorted.next = null;
while (head != null) {
ListNode current = head;
head = head.next;
if (current.val <= sorted.val) {
current.next = sorted;
sorted = current;
} else {
ListNode ptr = sorted;
while (ptr.next != null && ptr.next.val < current.val) {
ptr = ptr.next;
}
current.next = ptr.next;
ptr.next = current;
}
}
return sorted;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* insertionSortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* sorted = head;
head = head->next;
sorted->next = NULL;
while (head) {
ListNode* current = head;
head = head->next;
if (current->val <= sorted->val) {
current->next = sorted;
sorted = current;
} else {
ListNode* ptr = sorted;
while (ptr->next && ptr->next->val < current->val) {
ptr = ptr->next;
}
current->next = ptr->next;
ptr->next = current;
}
}
return sorted;
}class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function insertionSortList(head) {
if (!head || !head.next) return head;
let sorted = head;
head = head.next;
sorted.next = null;
while (head) {
let current = head;
head = head.next;
if (current.val <= sorted.val) {
current.next = sorted;
sorted = current;
} else {
let ptr = sorted;
while (ptr.next && ptr.next.val < current.val) {
ptr = ptr.next;
}
current.next = ptr.next;
ptr.next = current;
}
}
return sorted;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* insertionSortList(struct ListNode* head) {
if (!head || !head->next) return head;
struct ListNode* sorted = head;
head = head->next;
sorted->next = NULL;
while (head) {
struct ListNode* current = head;
head = head->next;
if (current->val <= sorted->val) {
current->next = sorted;
sorted = current;
} else {
struct ListNode* ptr = sorted;
while (ptr->next && ptr->next->val < current->val) {
ptr = ptr->next;
}
current->next = ptr->next;
ptr->next = current;
}
}
return sorted;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode InsertionSortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode sorted = head;
head = head.next;
sorted.next = null;
while (head != null) {
ListNode current = head;
head = head.next;
if (current.val <= sorted.val) {
current.next = sorted;
sorted = current;
} else {
ListNode ptr = sorted;
while (ptr.next != null && ptr.next.val < current.val) {
ptr = ptr.next;
}
current.next = ptr.next;
ptr.next = current;
}
}
return sorted;
}
}Python provides an in-place sorting solution, managing nodes directly in the linked list. By transitioning each node one by one into the sorted area, it cleverly rearranges through pointer adjustments without extra structures.
Time Complexity: O(n2) for orderly sequential node insertions.
Space Complexity: O(1), since it only uses node adjustments for resolution.
Approach 3: Default Approach
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func insertionSortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
dummy := &ListNode{head.Val, head}
pre, cur := dummy, head
for cur != nil {
if pre.Val <= cur.Val {
pre = cur
cur = cur.Next
continue
}
p := dummy
for p.Next.Val <= cur.Val {
p = p.Next
}
t := cur.Next
cur.Next = p.Next
p.Next = cur
pre.Next = t
cur = t
}
return dummy.Next
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Insertion into New List | Time Complexity: O(n2), indicated by nested loops for node placements. |
| Approach 2: In-place Insertion in the List | Time Complexity: O(n2) for orderly sequential node insertions. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Insertion into New List | O(n^2) | O(1) | Best for understanding insertion sort mechanics on linked lists |
| In-place Insertion in the List | O(n^2) | O(1) | Preferred in interviews; modifies the list directly and avoids rebuilding |
Frequently asked questions
Is Insertion Sort List easy or hard?
Insertion Sort List is generally rated Medium difficulty. The sorting idea is simple, but correctly manipulating linked list pointers without losing nodes requires careful implementation.
Insertion Sort List Python/Java solution
Most implementations use a dummy head and iterate through the list while inserting each node into its correct position. The same logic works across Python, Java, C++, C#, and JavaScript because it only relies on pointer or reference updates between nodes.
How to solve Insertion Sort List in O(n)?
A strict insertion sort on a linked list cannot guarantee O(n) time for arbitrary input. The worst case always reaches O(n^2). However, if the list is already nearly sorted, the in-place method often runs close to O(n) because very few nodes need repositioning.
What is the best approach for Insertion Sort List?
The in-place insertion approach is typically considered the best. It keeps a sorted prefix of the list and only relocates nodes that break the order. This demonstrates strong pointer manipulation skills and maintains O(n^2) time with O(1) extra space.
Is Insertion Sort List asked at Google/Amazon/Meta?
Linked list sorting and pointer manipulation problems are common in interviews at companies like Amazon, Meta, and Google. Variants of insertion sort on linked lists appear in interview prep platforms because they test pointer handling and algorithm fundamentals.
What data structure is used in Insertion Sort List?
The problem operates entirely on a singly linked list. A dummy head node is commonly used to simplify insertion logic, allowing nodes to be inserted at the beginning of the sorted portion without special edge-case handling.
What is the time complexity of Insertion Sort List?
Insertion sort on a linked list runs in O(n^2) time in the worst case because each node insertion may require scanning the already sorted portion of the list. The algorithm uses only pointer updates, so the auxiliary space complexity is O(1).