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:
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:
[1, 5000].-5000 <= Node.val <= 5000The key idea behind Insertion Sort on a Linked List is similar to the array version: build a sorted portion of the list one node at a time. Instead of shifting elements like in arrays, we adjust node pointers to place each element in its correct position.
A common strategy is to maintain a dummy head that represents the start of the sorted list. Traverse the original list and, for each node, find the correct insertion position within the already sorted part. This involves scanning from the dummy node until the right location is found, then inserting the current node by updating its next pointers.
This approach works well for linked lists because insertion operations are efficient once the correct position is identified. However, finding that position may require scanning the sorted section, leading to a quadratic time complexity in the worst case. The advantage is that the algorithm performs sorting in-place without requiring additional memory.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Insertion Sort with Dummy Node | O(n^2) | O(1) |
NeetCode
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.
Time Complexity: O(n2) in the worst case, where n is the number of nodes. This is due to iteratively inserting elements in order.
Space Complexity: O(1), as we use a constant amount of extra space other than the input list.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode
The code defines a function that sorts a linked list using insertion sort. It iterates over the original list, taking each node, and inserts it into the correct position in a new, sorted list. Specifically, it maintains a sorted list 'sortedHead' and iteratively places each node from the original list into this new list in sorted order.
Instead of creating a new list, this approach involves sorting the nodes within the existing linked list, rearranging the pointers directly.
Time Complexity: O(n2), due to each node insertion operation scanning the sequence.
Space Complexity: O(1), as no new nodes are created—existing nodes are relinked.
1public class ListNode {
2 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;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Insertion sort works well for linked lists because inserting a node only requires updating pointers rather than shifting elements. Once the correct position is found, the insertion operation is constant time.
Yes, linked list sorting problems like Insertion Sort List appear in coding interviews at major tech companies. They test understanding of pointer manipulation, list traversal, and algorithmic complexity.
The optimal approach simulates insertion sort directly on the linked list. Using a dummy head node, each element from the original list is inserted into the correct position in the sorted portion. This keeps the algorithm simple and avoids extra memory usage.
A singly linked list with pointer manipulation is the primary data structure used. A dummy node is often added at the beginning to simplify insertions at the head of the sorted list.
C# retains the logic in-place by directly organizing nodes within the list. By moving nodes directly, it requires keen pointer management to ensure seamless sorting with minimal overhead.