Insertion Sort List

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

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

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* insertionSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    
    struct ListNode* prev = head;
    struct ListNode* current = head->next;
    
    while (current != NULL) {
        if (prev->val > current->val) {
            struct ListNode* temp = dummy;
            while (temp->next->val < current->val) {
                temp = temp->next;
            }
            prev->next = current->next;
            current->next = temp->next;
            temp->next = current;
            current = prev->next;
        } else {
            prev = current;
            current = current->next;
        }
    }
    
    return dummy->next;
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val = 0, ListNode next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public ListNode InsertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode curr = head;
        
        while (curr != null) {
            ListNode prev = dummy;
            ListNode nextNode = curr.next;
            
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }
            
            curr.next = prev.next;
            prev.next = curr;
            curr = nextNode;
        }
        
        return dummy.next;
    }
}

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

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function insertionSortList(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return head;
    
    let dummy = new ListNode(0);
    dummy.next = head;
    let current = head;
    while (current && current.next) {
        if (current.val <= current.next.val) {
            current = current.next;
        } else {
            let innerCurrent = dummy;
            while (innerCurrent.next.val < current.next.val) {
                innerCurrent = innerCurrent.next;
            }
            let temp = current.next;
            current.next = temp.next;
            temp.next = innerCurrent.next;
            innerCurrent.next = temp;
        }
    }
    
    return dummy.next;
}

                                            
class Solution {
    fun insertionSortList(head: ListNode?): ListNode? {
        if (head == null || head.next == null) {
            return head
        }
        
        var dummy = ListNode(0)
        var prev = dummy
        var curr = head
        
        while (curr != null) {
            var next = curr.next
            
            if (prev.next != null && prev.next!!.`val` > curr.`val`) {
                prev = dummy
            }
            
            while (prev.next != null && prev.next!!.`val` < curr.`val`) {
                prev = prev.next!!
            }
            
            curr.next = prev.next
            prev.next = curr
            
            curr = next
        }
        
        return dummy.next
    }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0, Next: nil}
    prev := dummy
    curr := head

    for curr != nil {
        next := curr.Next
        for prev.Next != nil && prev.Next.Val < curr.Val {
            prev = prev.Next
        }
        curr.Next = prev.Next
        prev.Next = curr
        prev = dummy
        curr = next
    }

    return dummy.Next
}

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var x: Int = _x
 *   var next: ListNode = _next
 * }
 */

object Solution {
    def insertionSortList(head: ListNode): ListNode = {
        if (head == null || head.next == null) return head
        
        val dummy = new ListNode()
        var curr = head
        var prev = dummy
        var next: ListNode = null
        
        while (curr != null) {
            next = curr.next
            while (prev.next != null && prev.next.x < curr.x) {
                prev = prev.next
            }
            curr.next = prev.next
            prev.next = curr
            prev = dummy
            curr = next
        }
        
        dummy.next
    }
}

To solve this coding challenge, we will utilize the insertion sort algorithm to sort a singly linked list. The insertion sort algorithm is particularly effective for small or partially sorted lists, as it iteratively moves through the list, extracting elements one at a time and inserting them into their correct position in a growing sorted portion of the list.

# Explanation

Insertion sort works by dividing the list into a sorted and an unsorted region. Initially, the sorted region contains only the first element of the list. The algorithm then takes elements from the unsorted region one at a time and inserts them into their correct position within the sorted region. Here’s a high-level approach to solving this problem:

Edge Case : If the list is empty or contains only one element, it is already sorted.
Use a Dummy Node : Introduce a dummy node at the beginning to simplify edge case handling, particularly for elements that need to be inserted at the head.
Iterate Through the List : Use pointers to traverse the list and perform the insertion sort.
Find the Correct Position : For each node, find the appropriate position in the sorted region and insert it there.
Update Pointers : Adjust the pointers to maintain the sorted region and continue the process until all elements are sorted.

Step-by-Step Explanation

Initialization : Start with a dummy node to handle edge cases.
Traversal : Traverse the list with a pointer (
current

) to process each node.
Condition Check : If the current node's value is less than or equal to the next node's value, move to the next node.
Node Repositioning : If not, find the correct position in the sorted part using another pointer (
prev

).
Re-Insertion : Remove the node from its current location and insert it after the
prev

node.
Repeat : Continue this process until the list is fully sorted.

Detailed Steps in Pseudocode

                                            
Function insertionSortList(head):
    # Edge case: If head is null or only one element, return head
    If head == null OR head.next == null:
        Return head

    # Create a dummy node to ease insertion at the head
    dummy = new ListNode(0)
    dummy.next = head

    # Current node starts from the head
    current = head

    # Traverse the list with the current pointer
    While current != null AND current.next != null:
        
        # If the current value is less or equal to the next value, move to the next node
        If current.val <= current.next.val:
            current = current.next
        
        # Otherwise, we need to insert current.next into the sorted part
        Else:
            # Remove the node to be repositioned
            reposition_node = current.next
            current.next = reposition_node.next

            # Find the correct position in the sorted part
            prev = dummy
            While prev.next.val < reposition_node.val:
                prev = prev.next

            # Insert the node after the found position
            reposition_node.next = prev.next
            prev.next = reposition_node

    # Return the sorted list, which is dummy.next
    Return dummy.next

# Pseudocode Breakdown

                                            
Function insertionSortList(head):
    If head == null OR head.next == null:  # Check for an empty list or single element list
        Return head

    dummy = new ListNode(0)  # Dummy node as a sorted list starting point
    dummy.next = head

    current = head  # Pointer to start traversing the list

    While current != null AND current.next != null:  # Continue until reaching the end of the list
        If current.val <= current.next.val:  # If the current node is in correct order
            current = current.next  # Move to the next node

        Else:  # Node needs to be repositioned
            reposition_node = current.next  # Node to be repositioned
            current.next = reposition_node.next  # Remove it from the list

            prev = dummy  # Pointer to find the correct position in the sorted part
            While prev.next.val < reposition_node.val:  # Find where to insert
                prev = prev.next  # Move prev to next node

            reposition_node.next = prev.next  # Link reposition_node to the sorted part
            prev.next = reposition_node  # Insert the node after prev

    Return dummy.next  # Return the sorted list

This detailed approach ensures every step is clear and logically follows the insertion sort paradigm, applied specifically to singly linked lists. The dummy node simplifies edge cases and maintains a clean structure.