关于这道题，我实在想不通为何被列入了 Medium 的行列，插入排序是知乎上有名的梗，如果这个算法不能在十分钟内流畅的写出来，应该万般羞愧的躲进活死人墓，苦练各种基本功。

简单过一下插入排序的过程吧：

[3 7] 4 9 5 2 6 1
^   ^
[3 4 7 9] 5 2 6 1
^     ^
[3 4 5 7 9] 2 6 1
^           ^
[2 3 4 5 7 9] 6 1
^     ^
[2 3 4 5 6 7 9] 1
^               ^
[1 2 3 4 5 6 7 9]

从上述过程中，可以看出，每一次遇到逆序情况(即 7->4, 9->5, 9->2, 9->6, 9->1 等情况)时，都需要从头开始比对，遇到合适的位置，便将当前元素插过去。所以算法的核心是：

1->3->4->2->5 => 1->2->3->4->5
 ^    ^
i  p pNode

的过程如何实现。假设当前指针为 p，要插入的节点指针 pNode，从头检测的指针为 i, 则有：

ListNode *pNode = p->next;
p->next = pNode->next;
pNode->next = i->next;
i->next = pNode;

如果看不太明白，还需要动手在纸上画一画，链表题如果不动手，的确是很难理清楚的。