147. Insertion Sort List

https://leetcode.com/problems/insertion-sort-list

Python

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        new_head = ListNode(val=-5001, next=None)
        origin = head

        while origin:
            cur = new_head
            while cur.next and cur.next.val < origin.val:
                cur = cur.next

            cur.next = ListNode(val=origin.val, next=cur.next if cur.next else None)
            origin = origin.next

        return new_head.next