05 Jun 2024•Python•Unknown

Insertion Sort List

notes and solution files for insertion sort list.

this entry collects the solution files i have for insertion sort list. i may expand it with a fuller write-up later, but the implementation files are already here.

available solution files

Python insertion-sort-list/solution.py

Solution files

Python•insertion-sort-list/solution.py

from typing import Optional


class ListNode:
    def __init__(self, val: int = class="syntax-number">0, next: class="syntax-string">"Optional[ListNode]" = None) -> None:
        self.val = val
        self.next = next


class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None

        dummy = ListNode(-class="syntax-number">10**class="syntax-number">9)
        current = head

        while current:
            next_unsorted = current.next
            prev = dummy
            while prev.next and prev.next.val < current.val:
                prev = prev.next

            current.next = prev.next
            prev.next = current
            current = next_unsorted

        return dummy.next