[Python] Actual Insertion Sort (solution article has inaccurate implementation)
Strictly speaking, in insertion sort, the intermeidate sorted list is iterated backwards (we first compare the new item with the last item and swap if they are 
Strictly speaking, in insertion sort, the intermeidate sorted list is iterated backwards (we first compare the new item with the last item and swap if they are out of order: this is repeated until new item is in order with previous item)\nHowever, in the solution article and some other posts, the intermediate sorted list is iterated forwards.  This still produces correct output and the time complexity either way is still O(n^2).  However, I believe we should implement the strict form for two reasons:\n* Insertion sort is particularly efficient for partially sorted array, and the benefit only exists if intermediate array is iterated backwards\n* Iterating singly linked list forwards is straightforward, but it\'s challenging to iterate it backwards.  I figured this is what makes this problem challenging (and thus interesting)\n\nThe way I approach this is to keep intermediate sorted list in *descending* order to work around single linkage.  After we have a descending array, we simply need to revert the linkage of the list by iterating the array one more time.  For partially sorted array (list), this ensures a O(n) time complexity.\n\n```python\n# Definition for singly-linked list.\n# class ListNode:\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution:\n    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n        # the intermidiate sorted list is in descending order so that strict insertion sort is possible\n        # lastly, reverse the sorted list\n        sentinel = ListNode(0, head)\n        node = head.next\n        head.next = None\n        while node:\n            next_node = node.next\n            \n            prior = sentinel\n            while prior.next and prior.next.val > node.val:\n                prior = prior.next\n            node.next = prior.next\n            prior.next = node\n            \n            node = next_node\n        \n        node = sentinel.next  # node to be modified\n        head = None  # track the head of reversed list\n        while node:\n            next_node = node.next\n            \n            node.next = head\n            head = node\n            \n            node = next_node\n            \n        return head\n```
[]