[LeetCode]147. 對連結清單進行插入排序

147. 對連結清單進行插入排序

難度：中等

對連結清單進行插入排序。

插入排序的動畫示範如上。從第一個元素開始，該連結清單可以被認為已經部分排序（用黑色表示）。

每次疊代時，從輸入資料中移除一個元素（用紅色表示），并原地将其插入到已排好序的連結清單中。

插入排序算法：

1. 插入排序是疊代的，每次隻移動一個元素，直到所有元素可以形成一個有序的輸出清單。
2. 每次疊代中，插入排序隻從輸入資料中移除一個待排序的元素，找到它在序列中适當的位置，并将其插入。
3. 重複直到所有輸入資料插入完為止。

示例 1：

輸入: 4->2->1->3
輸出: 1->2->3->4
           

示例 2：

輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
           

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        List = ListNode()

        while head:
            cur = List
            while cur.next and cur.next.val < head.val:
                cur = cur.next
            p = head
            head = head.next
            p.next = cur.next
            cur.next = p

        return List.next