题目
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
输入: head = [4,2,1,3] 输出: [1,2,3,4]
题解
我们在insertionSortList函数中接收一个头结点head作为输入，在首先定义了三个变量：retHead、retPrev和curr。retHead用于记录已排序链表的头结点，retPrev用于记录已排序链表的前一个节点，curr则是当前需要插入的节点，然后进入while循环，首先记录下一个需要插入的节点next，然后将当前节点的next属性设为null，这是因为在插入排序中，每次将一个节点插入到已排序部分中，需要将该节点的next属性设为null，然后将当前节点插入到已排序的链表中，这里通过调用insertNode函数实现的，插入后返回的头结点retHead将作为下一次迭代的基础，最后，当整个链表都被遍历完成后，返回排好序的链表，在insertNode函数中，首先定义了两个变量：curr和prev，它们分别用于遍历已排序的链表和记录当前节点的前一个节点，接着进入while循环，每次遍历都记录下一个节点的位置next，然后判断当前节点是否应该插入到当前节点的前面。如果是，就将该节点插入到已排序链表中，并返回新的头结点head，如果当前节点不应该插入到当前节点的前面，则继续遍历链表，将prev和curr指针向后移动，当已排序链表中的所有节点都遍历完后，如果当前节点需要插入到链表的末尾，则将其插入到链表中，并返回头结点head。如果链表为空，则将该节点作为新的头结点返回。
function insertionSortList (head) { let retHead = null let retPrev = null let curr = head while (curr) { const next = curr.next curr.next = null retHead = insertNode(retHead, curr) curr = next } return retHead }; function insertNode(head, node) { let curr = head let prev = null while (curr) { const next = curr.next if (node.val < curr.val) { if (!prev) { node.next = head return node } else { prev.next = node node.next = curr return head } } prev = curr curr = next } if (prev) { prev.next = node return head } else { return node } }
