Description
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.
Examples:
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]Solution in Python
Python
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
# If the list is empty or has only one element, it's already sorted
if not head or not head.next:
return head
# Create a new dummy head for the sorted portion of the list
dummy = ListNode(0)
dummy.next = head
current = head.next
head.next = None
# Process each element in the list
while current:
# Remember the next element to be processed
next_to_process = current.next
# Find the position to insert the current element
prev = dummy
while prev.next and prev.next.val < current.val:
prev = prev.next
# Insert the current element in the correct position
current.next = prev.next
prev.next = current
# Move to the next element
current = next_to_process
return dummy.nextExplanation:
- ListNode Class:
- A simple class definition for the nodes of the singly linked list. Each node contains a value (
val) and a reference to the next node (next).
- A simple class definition for the nodes of the singly linked list. Each node contains a value (
- insertionSortList Method:
- The method takes the head of the linked list and returns the head of the sorted list.
- Initial Checks:
- If the list is empty (
headisNone) or contains only one element (head.nextisNone), it is already sorted. So, returnhead.
- If the list is empty (
- Dummy Head:
- Create a new dummy head node (
dummy). This node helps to easily manage the head of the sorted portion of the list. - Initialize the
dummy.nextto the original head, and setcurrentto the second node (head.next). - Break the link between the first and second nodes (
head.next = None), making the first node the start of the sorted list.
- Create a new dummy head node (
- Insertion Sort Process:
- Iterate through each node starting from
current. - For each node, remember the next node to process (
next_to_process = current.next). - Find the correct position to insert the
currentnode in the sorted part of the list using aprevpointer that starts atdummy. - Traverse the sorted part of the list until finding the correct insertion point (
prev.next.val < current.val). - Insert the
currentnode betweenprevandprev.next. - Move to the next node to process (
current = next_to_process).
- Iterate through each node starting from
- Return the Sorted List:
- The sorted list starts from
dummy.next.
- The sorted list starts from
This algorithm effectively grows a sorted list by iteratively taking nodes from the input list and inserting them in the correct position within the sorted list. It ensures that at each step, the sorted list remains ordered.
Solution in Javascript
JavaScript
/**
* @param {ListNode} head
* @return {ListNode}
*/
var insertionSortList = function(head) {
// If the list is empty or has only one element, it's already sorted
if (!head || !head.next) {
return head;
}
// Create a new dummy head for the sorted portion of the list
const dummy = new ListNode(0);
dummy.next = head;
let current = head.next;
head.next = null;
// Process each element in the list
while (current) {
// Remember the next element to be processed
let nextToProcess = current.next;
// Find the position to insert the current element
let prev = dummy;
while (prev.next && prev.next.val < current.val) {
prev = prev.next;
}
// Insert the current element in the correct position
current.next = prev.next;
prev.next = current;
// Move to the next element
current = nextToProcess;
}
return dummy.next;
};Solution in Java
Java
class Solution {
public ListNode insertionSortList(ListNode head) {
// If the list is empty or has only one element, it's already sorted
if (head == null || head.next == null) {
return head;
}
// Create a new dummy head for the sorted portion of the list
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = head.next; // Start with the second node
head.next = null; // The first node is now considered sorted
// Process each element in the list
while (current != null) {
// Save the next node to process
ListNode nextToProcess = current.next;
// Find the position to insert the current element
ListNode prev = dummy;
while (prev.next != null && prev.next.val < current.val) {
prev = prev.next;
}
// Insert the current element in the correct position
current.next = prev.next;
prev.next = current;
// Move to the next node to process
current = nextToProcess;
}
// Return the sorted list starting from dummy.next
return dummy.next;
}
}Solution in C#
C#
public class Solution {
public ListNode InsertionSortList(ListNode head) {
// If the list is empty or has only one element, it's already sorted
if (head == null || head.next == null) {
return head;
}
// Create a new dummy head for the sorted portion of the list
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = head.next; // Start with the second node
head.next = null; // The first node is now considered sorted
// Process each element in the list
while (current != null) {
// Save the next node to process
ListNode nextToProcess = current.next;
// Find the position to insert the current element
ListNode prev = dummy;
while (prev.next != null && prev.next.val < current.val) {
prev = prev.next;
}
// Insert the current element in the correct position
current.next = prev.next;
prev.next = current;
// Move to the next node to process
current = nextToProcess;
}
// Return the sorted list starting from dummy.next
return dummy.next;
}
}