Problem Description

Given the head of a singly linked list head, sort the list using insertion sort and return the sorted list's head.

• You must sort the list in-place (i.e., you may not create a brand new list; instead, rearrange the existing nodes).
• Each node in the list contains an integer value.
• Do not reuse or copy node values; only rearrange the nodes themselves.
• The final result must be a valid singly linked list with all original nodes, sorted in ascending order.

Thought Process

To solve this problem, we can draw inspiration from the classic insertion sort algorithm, which is often used for sorting arrays. The key idea is to build a sorted portion of the list one node at a time by inserting each node into its correct position. However, unlike arrays, linked lists do not allow random access to elements, so we have to traverse the list to find the correct insertion point for each node.

A brute-force approach would be to repeatedly search for the smallest node and move it to the front, but this would be inefficient. Instead, by mimicking how insertion sort works, we can efficiently insert each node into its proper place in the sorted portion of the list as we traverse it.

The challenge is to manipulate the pointers correctly, ensuring that we do not lose track of any nodes or create cycles in the list.

Solution Approach

Here’s a step-by-step approach to implementing insertion sort on a singly linked list:

1. Use a Dummy Node: Create a dummy node before the head. This simplifies insertion logic, especially when inserting at the head of the list.
2. Iterate Through the List: Use a pointer (current) to traverse the list. For each node, determine if it is already in the correct position (i.e., its value is greater than or equal to the previous node's value). If so, move forward.
3. Find Insertion Position: If the current node is out of order, use a second pointer (prev) starting from the dummy node to find where in the sorted portion the current node should go.
4. Rearrange Pointers: Remove the current node from its current position and insert it after prev.
5. Repeat: Continue this process for all nodes until the end of the list is reached.

This approach ensures that at each step, the portion of the list before current is always sorted.

Example Walkthrough

Let's walk through an example with the input list: 4 -> 2 -> 1 -> 3

1. Start: The sorted list is empty (dummy node points to null).
2. Insert 4: Since the sorted list is empty, insert 4 after dummy. Now: dummy -> 4
3. Insert 2: Traverse from dummy. 2 < 4, so insert 2 before 4. Now: dummy -> 2 -> 4
4. Insert 1: Traverse from dummy. 1 < 2, so insert 1 before 2. Now: dummy -> 1 -> 2 -> 4
5. Insert 3: Traverse from dummy. 3 > 2 but 3 < 4, so insert 3 between 2 and 4. Now: dummy -> 1 -> 2 -> 3 -> 4

Final sorted list: 1 -> 2 -> 3 -> 4

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        curr = head
        while curr:
            prev = dummy
            # Find the right place to insert curr
            while prev.next and prev.next.val < curr.val:
                prev = prev.next
            next_temp = curr.next
            # Insert curr between prev and prev.next
            curr.next = prev.next
            prev.next = curr
            curr = next_temp
        return dummy.next
      

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dummy(0);
        ListNode* curr = head;
        while (curr) {
            ListNode* prev = &dummy;
            while (prev->next && prev->next->val < curr->val) {
                prev = prev->next;
            }
            ListNode* next_temp = curr->next;
            curr->next = prev->next;
            prev->next = curr;
            curr = next_temp;
        }
        return dummy.next;
    }
};
      

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode curr = head;
        while (curr != null) {
            ListNode prev = dummy;
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }
            ListNode nextTemp = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = nextTemp;
        }
        return dummy.next;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function(head) {
    let dummy = new ListNode(0);
    let curr = head;
    while (curr !== null) {
        let prev = dummy;
        while (prev.next !== null && prev.next.val < curr.val) {
            prev = prev.next;
        }
        let nextTemp = curr.next;
        curr.next = prev.next;
        prev.next = curr;
        curr = nextTemp;
    }
    return dummy.next;
};
      

Time and Space Complexity

• Brute-force approach: If you repeatedly scan the list to find the smallest node and move it, the time complexity is O(n^2) because for each node, you may traverse the entire list.
• Optimized insertion sort approach: The time complexity is still O(n^2) in the worst case (e.g., a reversed list), as each insertion may require traversing the sorted portion of the list. However, if the list is already partially sorted, performance improves.
• Space complexity: Both approaches use O(1) additional space because sorting is done in place, and only a few pointers are used.

The main benefit of the optimized approach is that it avoids unnecessary node copying and always maintains a valid, sorted portion of the list.

Summary

In summary, insertion sort is well-suited for sorting linked lists because it can efficiently insert nodes without shifting elements, as would be required in an array. By carefully managing pointers and using a dummy node, we can sort the list in place with minimal extra memory. The solution is elegant because it leverages the properties of linked lists and the simplicity of insertion sort, making it easy to implement and understand.