Leetcode 147. Insertion Sort List
Problem Explanation
This problem is about sorting an unsorted linked list by using insertion sort. Insertion sort is an iterative algorithm that creates a sorted list by placing each input element in the correct position within that list.
Here's how the algorithm works:
- Consider the first node in the list as a
sorted
list and the rest as anunsorted
list. - Remove one node from the
unsorted
list and insert it into the correct position in thesorted
list. - Continue the process until the
unsorted
list is empty.
Let's consider this example: 4->2->1->3
- In the first step, consider node
4
as thesorted
list: [sorted: 4] [unsorted: 2->1->3] - Take node
2
fromunsorted
and insert it before4
insorted
: [sorted: 2->4] [unsorted: 1->3] - Repeat this process till the
unsorted
list is empty: [sorted: 1->2->3->4] [unsorted: ]
The resulting sorted list is 1->2->3->4.
Solution Approach
The algorithm iterates through each node in the linked list, and for each node, it finds the correct position in the sorted part of the list and inserts the node at that position.
The dummy node is used as a pseudo head of the sorted list. The pseudo head is useful because the head of the sorted list can change during the sorting process, and using a pseudo head simplifies handling of this special case.
Python Solution
1 2python 3# Definition for singly-linked list. 4# class ListNode: 5# def __init__(self, x): 6# self.val = x 7# self.next = None 8 9class Solution: 10 def insertionSortList(self, head: ListNode) -> ListNode: 11 dummy_head = ListNode(0) # Create a pseudo head 12 13 while head: # Loop over the unsorted part 14 node = dummy_head # Reset the node to head of the sorted part 15 while node.next and node.next.val < head.val: # Find the insertion position 16 node = node.next 17 18 # Insert the node 19 next_node = head.next 20 head.next = node.next 21 node.next = head 22 head = next_node # Update head for next iteration 23 24 return dummy_head.next # Return the sorted list
Java Solution
1
2java
3// Definition for singly-linked list.
4// public class ListNode {
5// int val;
6// ListNode next;
7// ListNode(int x) { val = x; }
8// }
9
10class Solution {
11 public ListNode insertionSortList(ListNode head) {
12 ListNode dummy = new ListNode(0); // Create a pseudo head
13 ListNode node;
14
15 while (head != null) { // Loop over the unsorted part
16 node = dummy; // Reset the node to head of the sorted part
17 while (node.next != null && node.next.val < head.val) { // Find the insertion position
18 node = node.next;
19 }
20
21 // Insert the node
22 ListNode next = head.next;
23 head.next = node.next;
24 node.next = head;
25 head = next; // Update head for next iteration
26 }
27
28 return dummy.next; // Return the sorted list
29 }
30}
JavaScript Solution
1
2javascript
3// Definition for singly-linked list.
4// function ListNode(val, next) {
5// this.val = (val===undefined ? 0 : val)
6// this.next = (next===undefined ? null : next)
7// }
8
9var insertionSortList = function(head) {
10 let dummy = new ListNode(0); // Create a pseudo head
11 let node;
12
13 while (head !== null) { // Loop over the unsorted part
14 node = dummy; // Reset the node to head of the sorted part
15 while (node.next !== null && node.next.val < head.val) { // Find the insertion position
16 node = node.next;
17 }
18
19 // Insert the node
20 let next = head.next;
21 head.next = node.next;
22 node.next = head;
23 head = next; // Update head for next iteration
24 }
25
26 return dummy.next; // Return the sorted list
27};
C++ Solution
1
2cpp
3// Definition for singly-linked list.
4// struct ListNode {
5// int val;
6// ListNode *next;
7// ListNode(int x) : val(x), next(NULL) {}
8// };
9
10class Solution {
11public:
12 ListNode* insertionSortList(ListNode* head) {
13 ListNode dummy(0); // Create a pseudo head
14 ListNode* node;
15
16 while (head) { // Loop over the unsorted part
17 node = &dummy; // Reset the node to head of the sorted part
18 while (node->next && node->next->val < head->val) { // Find the insertion position
19 node = node->next;
20 }
21
22 // Insert the node
23 ListNode* next = head->next;
24 head->next = node->next;
25 node->next = head;
26 head = next; // Update head for next iteration
27 }
28
29 return dummy.next; // Return the sorted list
30 }
31};
C# Solution
1
2csharp
3// Definition for singly-linked list.
4// public class ListNode {
5// public int val;
6// public ListNode next;
7// public ListNode(int val=0, ListNode next=null) {
8// this.val = val;
9// this.next = next;
10// }
11// }
12
13public class Solution {
14 public ListNode InsertionSortList(ListNode head) {
15 ListNode dummy = new ListNode(0); // Create a pseudo head
16 ListNode node;
17
18 while (head != null) { // Loop over the unsorted part
19 node = dummy; // Reset the node to head of the sorted part
20 while (node.next != null && node.next.val < head.val) { // Find the insertion position
21 node = node.next;
22 }
23
24 // Insert the node
25 ListNode next = head.next;
26 head.next = node.next;
27 node.next = head;
28 head = next; // Update head for next iteration
29 }
30
31 return dummy.next; // Return the sorted list
32 }
33}
These solutions iteratively sort through a singly-linked list using the Insertion Sort algorithm. They establish a "pseudo-head" for the sorted portion of the list so there are no issues if the head of the list changes.
One by one, they pull values from the unsorted section and place them in their correct position in the sorted portion. The sorted section grows until the unsorted section is empty, leaving us with a fully sorted singly-linked list.
All of these solutions are relatively efficient, with time complexities of O(n^2) due to the nested loop structure iterating through the linked list. It should be noted, however, that insertion sort is not the most efficient method for sorting a list of a large number of elements; other methods, such as quick sort or merge sort, would be better suited for larger data sets.
It's also important to remember that these solutions rely on the structure of the linked list class, specifically that each node holds a value and a reference to the next node. Therefore, proper usage implies that these classes have already been defined and implemented as per the given examples.
These solutions are versatile and can be easily modified or incorporated into larger programs requiring the use of sorted linked lists. They provide a good foundation for grappling with linked lists and the concept of sorting algorithms.
In conclusion, although insertion sort may not be the most efficient sorting algorithm, these implementations still offer simple and effective ways to sort linked lists in various programming languages.
Always remember to choose the sorting algorithm that best fits the immediate needs of your software, requiring you to take into consideration factors like the number of elements to sort and the nature of your data.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.