My C++ solution
ListNode *insertionSortList(ListNode *head)\n    {\n    \tif (head == NULL || head->next == NULL)\n    \t\treturn head;\n    \n    \tListNode *p = head->next;\n
    ListNode *insertionSortList(ListNode *head)\n    {\n    \tif (head == NULL || head->next == NULL)\n    \t\treturn head;\n    \n    \tListNode *p = head->next;\n    \thead->next = NULL;\n    \n    \twhile (p != NULL)\n    \t{\n    \t\tListNode *pNext = p->next;    /*store the next node to be insert*/\n    \t\tListNode *q = head;\n    \n    \t\tif (p->val < q->val)    /*node p should be the new head*/\n    \t\t{\n    \t\t\tp->next = q;\n    \t\t\thead = p;\n    \t\t}\n    \t\telse \n    \t\t{\n    \t\t\twhile (q != NULL && q->next != NULL && q->next->val <= p->val)\n    \t\t\t\tq = q->next;\n    \t\t\tp->next = q->next;\n    \t\t\tq->next = p;\n    \t\t}\n    \n    \t\tp = pNext;\n    \t}\n    \treturn head;\n    }
[]