Insertion Sort List Leetcode Problem 147 [Python Solution]
In this blog post, we're going to tackle the Insertion Sort List problem from LeetCode.
This is a medium-level problem that falls under the category of Linked Lists and is frequently asked in interviews, including at companies like Microsoft.
We will provide you with a step-by-step solution in Python.
Problem Overview
The problem statement is as follows:
Given the head of a singly linked list, sort the list using insertion sort and return the sorted list's head.
The insertion sort algorithm works by iterating through the list, consuming one element each time, and growing a sorted output list.
At each iteration, it removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
This process repeats until no input elements remain.
Let's visualize this algorithm:
Example 1:
Suppose we have an input linked list: [4, 2, 1, 3]
The expected output is a sorted linked list: [1, 2, 3, 4]
Example 2:
Input: head = [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]
Understanding the Constraints
Before diving into the solution, let's understand the constraints and the approach we need to take:
- The number of nodes in the list is in the range [1, 5000].
- Node values are in the range of -5000 to 5000. The main goal is to implement the insertion sort algorithm efficiently to handle the worst-case scenario while considering the edge cases.
Insertion Sort List LeetCode Problem Solution
1. Bruteforce Approach
One way to approach this problem is to simulate the insertion sort algorithm step by step.
We will start by initializing a dummy node and two pointers: prev and curr.
The prev pointer is used to track the last node of the sorted part, and the curr pointer is used to iterate through the unsorted part.
Here's the Python code for the bruteforce approach:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insertionSortList(head):
if not head or not head.next:
return head
# Initialize a sentinel node to simplify edge cases
sentinel = ListNode()
curr = head
while curr:
prev = sentinel
# Find the correct position to insert the current node
while prev.next and curr.val >= prev.next.val:
prev = prev.next
# Insert the current node in the correct position
curr.next, prev.next, curr = prev.next, curr, curr.next
return sentinel.next
This algorithm works by inserting each node from the unsorted part into its correct position within the sorted part.
It does this by iterating through the list once, making it efficient for nearly sorted lists, but it can have a worst-case time complexity of O(N^2) for reverse-sorted lists.
2. Efficient Approach with Reasoning
While the bruteforce approach provides a correct solution, it's not the most efficient way to perform insertion sort on a linked list.
A more optimized approach can achieve better results.
The key insight is to avoid unnecessary comparisons and swaps by checking if the current node is already in its correct position within the sorted portion.
We do this by comparing the current node's value with the next node's value, as this will help us determine if the current node is greater than or equal to the last node in the sorted portion.
The Python code for the efficient approach is as follows:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insertionSortList(head):
if not head or not head.next:
return head
# Initialize a sentinel node to simplify edge cases
sentinel = ListNode()
curr = head
while curr:
prev = sentinel
# Check if the current node is already in the correct position
if prev.next and curr.val >= prev.next.val:
prev = prev.next
else:
# Find the correct position to insert the current node
while prev.next and curr.val >= prev.next.val:
prev = prev.next
# Insert the current node in the correct position
curr.next, prev.next, curr = prev.next, curr, curr.next
return sentinel.next
This optimized approach reduces unnecessary comparisons and swaps, resulting in improved performance for nearly sorted lists.
While the worst-case time complexity remains O(N^2), it can significantly outperform the bruteforce approach in practice.
Time and Space Complexity
Now that we've discussed the solution, let's analyze its time and space complexity.
Time Complexity:
The time complexity of our efficient insertion sort algorithm is O(N^2) in the worst case.
This worst-case scenario occurs when the input linked list is sorted in reverse order, and for each node, we have to traverse the entire sorted portion of the list.
In the best-case scenario, when the input list is already sorted, the time complexity is O(N) because we don't need to perform many insertions or comparisons.
Space Complexity:
The space complexity is O(1) as we are not using any additional data structures that grow with the input size.
We are only manipulating the pointers of the existing linked list.
Reasoning Behind Our Approach
The reasoning behind our efficient insertion sort approach is to minimize unnecessary comparisons and swaps while keeping the worst-case time complexity in mind.
By first checking if the current node is already in its correct position within the sorted portion, we can avoid additional operations when the list is nearly sorted.
In the worst case, we may need to iterate through the sorted portion of the list for each node in the unsorted part, which results in a time complexity of O(N^2).
However, in practice, this approach performs well, especially for partially sorted lists, and can be a suitable solution for this problem.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
Related Interview Questions By Category:
Conclusion
In this blog post, we've tackled the Insertion Sort List problem from LeetCode.
We provided two solutions: a bruteforce approach and an optimized approach.
We discussed the reasoning behind the efficient approach, analyzed the time and space complexity, and demonstrated how this problem can be efficiently solved in Python.
We hope this guide helps you understand the problem and its solution better.
If you have any questions, suggestions, or comments, please feel free to ask.
You can also check out the LeetCode problem here to practice and explore further.
Don't forget to like and engage to support our content, and we look forward to helping you with more coding challenges in the future!
