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:

1. Consider the first node in the list as a sorted list and the rest as an unsorted list.
2. Remove one node from the unsorted list and insert it into the correct position in the sorted list.
3. Continue the process until the unsorted list is empty.

Let's consider this example: 4->2->1->3

1. In the first step, consider node 4 as the sorted list: [sorted: 4] [unsorted: 2->1->3]
2. Take node 2 from unsorted and insert it before 4 in sorted: [sorted: 2->4] [unsorted: 1->3]
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.