21_链表_147. 对链表进行插入排序.md

-- 链表 - mid 点击直达力扣

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

// 遍历链表得到数值并push进数组里面，将数组从小到大排序，最后新建链表
function insertionSortList(head: ListNode | null): ListNode | null {
    if (!head || !head.next) { return head }
    let array = []
    while (head) {
        array.push(head.val)
        head = head.next
    }
    array.sort((a, b) => a - b)
    let newHead = new ListNode(0)
    let curr = newHead
    for (let v of array) {
        curr.next = new ListNode(v)
        curr = curr.next
    }
    return newHead.next
};