链表的插入排序

由于单向链表只能单方向遍历，因此不能像数组的插入排序那样。

在这里使用递归实现，其有一个断链和合链的过程，这是代码的关键所在。

class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* insertionSortList(ListNode* head) {
        // write code here
        if (!head || !head->next) return head;
        ListNode dummyHead(0), *p;
        dummyHead.next = insertionSortList(head->next);
        p = &dummyHead;
        // 插入排序: 关键在于寻找插入位置
        while (p && p->next && p->next->val < head->val) { p = p->next; }
        head->next = p->next;
        p->next = head;
        return dummyHead.next;
    }
};