What is the time complexity of Insertion Sort List?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve Insertion Sort List?

This problem uses Linked List, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Insertion Sort List?

Insight 1: Using a dummy node simplifies the insertion process at the beginning of the sorted list, avoiding special case handling for inserting at the head. Insight 2: The core of insertion sort involves finding the correct insertion point in the already sorted portion of the list for each element from the unsorted portion.

Which companies ask LeetCode 147. Insertion Sort List in interviews?

This problem is frequently asked at Google.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Insertion Sort List - LeetCode 147 Solution

Insertion Sort List - Complete Solution Guide

Insertion Sort List is LeetCode problem 147, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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: 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 inse

Detailed Explanation

The problem requires sorting a singly linked list using the insertion sort algorithm. Insertion sort works by iteratively building a sorted sublist. For each element in the unsorted part of the list, we find its correct position within the sorted sublist and insert it there. The goal is to return the head of the fully sorted linked list.

Solution Approach

The solution implements insertion sort on a linked list. It uses a dummy node to represent the head of the sorted portion, which simplifies insertion operations, especially at the beginning. The algorithm iterates through the original list, taking each node and inserting it into the correct position within the sorted portion (starting from the dummy node). It does this by traversing the sorted portion until it finds the appropriate insertion point and then updates the `next` pointers accordingly.

Step-by-Step Algorithm

Step 1: Create a dummy node. This node's `next` pointer will point to the head of the sorted list (which is initially empty).
Step 2: Initialize `curr` to the head of the input linked list. This will be the node we want to insert into the sorted portion.
Step 3: While `curr` is not null, iterate through the unsorted portion of the list.
Step 4: For each `curr` node, find the correct position to insert it into the sorted portion. Start from `dummy` and iterate `prev` until `prev.next` is null or `prev.next.val` is greater than or equal to `curr.val`. This means `curr` should be inserted before `prev.next`.
Step 5: Save the `next` node of `curr` as `next_node` before modifying `curr`'s pointers. This preserves the unsorted part of the list.
Step 6: Insert `curr` between `prev` and `prev.next`: `curr.next = prev.next` and `prev.next = curr`.
Step 7: Move `curr` to the next node in the unsorted part of the list: `curr = next_node`.
Step 8: After iterating through all nodes in the original list, the linked list starting from `dummy.next` will be the sorted list. Return `dummy.next`.

Key Insights

Insight 1: Using a dummy node simplifies the insertion process at the beginning of the sorted list, avoiding special case handling for inserting at the head.
Insight 2: The core of insertion sort involves finding the correct insertion point in the already sorted portion of the list for each element from the unsorted portion.
Insight 3: Iterating and modifying linked list pointers requires careful management to avoid breaking the list and losing track of nodes.

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Sorting.

Companies

Asked at: Google.

Insertion Sort List | LeetCode 147

Medium

Linked List Sorting

Time: O(n^2)Space: O(1)

Solution Code

Available in:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode curr = head;

        while (curr != null) {
            // Find the correct position to insert the current node in the sorted list
            ListNode prev = dummy;
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }
            
            // Save the next node before we modify curr's pointers
            ListNode next_node = curr.next;
            
            // Insert curr between prev and prev.next
            curr.next = prev.next;
            prev.next = curr;
            
            // Move to the next node in the original list
            curr = next_node;
            
        }
        return dummy.next;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 147: Insertion Sort List - Detailed explanation and solution approaches.

Topics

Linked List Sorting

Companies

Google

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:147

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Create a dummy node. This node's `next` pointer will point to the head of the sorted list (which is initially empty).
2
Step 2: Initialize `curr` to the head of the input linked list. This will be the node we want to insert into the sorted portion.
3
Step 3: While `curr` is not null, iterate through the unsorted portion of the list.
4
Step 4: For each `curr` node, find the correct position to insert it into the sorted portion. Start from `dummy` and iterate `prev` until `prev.next` is null or `prev.next.val` is greater than or equal to `curr.val`. This means `curr` should be inserted before `prev.next`.
5
Step 5: Save the `next` node of `curr` as `next_node` before modifying `curr`'s pointers. This preserves the unsorted part of the list.
6
Step 6: Insert `curr` between `prev` and `prev.next`: `curr.next = prev.next` and `prev.next = curr`.
7
Step 7: Move `curr` to the next node in the unsorted part of the list: `curr = next_node`.
8
Step 8: After iterating through all nodes in the original list, the linked list starting from `dummy.next` will be the sorted list. Return `dummy.next`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n^2) because, for each of the 'n' nodes in the input list, we potentially need to traverse the already sorted portion, which can grow up to 'n' nodes in length. The space complexity is O(1) because we're only using a constant amount of extra space for pointers (dummy, curr, prev, next_node) regardless of the input size. No auxiliary data structures that scale with the input are used.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Merge Sort

Merge sort is a divide-and-conquer algorithm that can also be used to sort a linked list. It involves recursively dividing the list into smaller sublists, sorting them, and then merging them back together.

Time: O(n log n)Space: O(log n) due to recursion

Trade-offs: Merge sort generally provides better time complexity (O(n log n)) compared to insertion sort (O(n^2)). However, for very small lists, the overhead of recursion in merge sort might make insertion sort slightly faster. Merge sort typically requires O(log n) space due to the recursive calls whereas Insertion sort uses constant space. For very limited memory, insertion sort may be preferred.

Using an array/list

Copy the linked list values to an array, sort the array using an efficient sorting algorithm (like quicksort or mergesort which is O(n log n) on average), and then reconstruct the linked list from the sorted array.

Time: O(n log n)Space: O(n)

Trade-offs: This approach is generally faster (O(n log n) time) but uses O(n) extra space for the array. This is a space-time trade-off. If memory is a constraint or the list is very nearly sorted, the in-place insertion sort might be more suitable.

✨

Key Insights

1Insight 1: Using a dummy node simplifies the insertion process at the beginning of the sorted list, avoiding special case handling for inserting at the head.
2Insight 2: The core of insertion sort involves finding the correct insertion point in the already sorted portion of the list for each element from the unsorted portion.
3Insight 3: Iterating and modifying linked list pointers requires careful management to avoid breaking the list and losing track of nodes.

📚

Key Terms Explained

For Students

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty list: If the input list is empty (head is null), the while loop will not execute, and the function will correctly return dummy.next, which is null.
Edge case 2: List with one element: The outer while loop will execute once. The inner while loop may not execute at all, or it may execute once depending on the dummy node value. The insertion will be handled correctly, resulting in a list sorted with one element.
Edge case 3: List with duplicate values: The algorithm will correctly place duplicates in their sorted order. The inner while loop condition `prev.next.val < curr.val` ensures the insertion happens after all elements equal to curr.val in the sorted list.
Edge case 4: List already sorted: In the best-case scenario, the inner loop will always stop at the first check, so the outer loop runs n times and the inner loop runs almost zero times on average, but the algorithm is still O(n^2) in the best case.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to save the next node of 'curr' before modifying 'curr.next'. This can break the list, leading to an infinite loop or incorrect results.

✗Common mistake 2: Not handling the case where the new node needs to be inserted at the beginning of the sorted portion (before the first element). The dummy node simplifies this scenario and avoids an if-else block.

✗Common mistake 3: Incorrectly updating pointers during the insertion process. It's important to ensure the pointers are updated in the correct order to avoid breaking the list.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Sorting a playlist of songs as new songs are added. Insertion sort's efficiency on nearly sorted data could be beneficial if the playlist is mostly sorted already.

🏦Real-world scenario 2: Maintaining an ordered list of tasks in a process scheduler where tasks are dynamically added and need to be kept in priority order. In situations where the dataset size remains relatively small, insertion sort offers a simple and effective approach.

🎮Real-world scenario 3: In embedded systems with limited memory, insertion sort can be a suitable choice due to its constant space complexity.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The dummy node technique prevents edge cases. For cycle detection, Floyd's algorithm is the standard. Always handle empty list and single node cases.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Losing reference to nodes when modifying pointers. Use temporary variables to save references.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 26, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

How does the fast/slow pointer technique work?

Fast pointer moves 2 steps while slow moves 1 step. When fast reaches the end, slow is at middle. If there's a cycle, they will meet. This technique is used for: finding middle node, detecting cycles, finding cycle start point, and checking palindromes.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Insertion Sort List"?

For this medium-level Linked List problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether sorting techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?