class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head == NULL) return NULL;
        ListNode* sorted_head = head;
        ListNode* unsorted_head = head->next;
        head->next = NULL;
        
        ListNode* cur = unsorted_head;

        while (cur != NULL) {
            unsorted_head = cur->next;
            cur->next = NULL;
            sorted_head = insertNode(sorted_head, cur);
            cur = unsorted_head;
        }
        
        return sorted_head;
    }
    
    ListNode* insertNode(ListNode* list, ListNode* node) {
        if (list == NULL && node == NULL) return NULL;
        if (node == NULL) return list;
        if (list == NULL) return node;
        ListNode* cur = list;
        ListNode* pre = NULL;
        while (cur != NULL && cur->val < node->val) {
            pre = cur;
            cur = cur->next;
        }
        if (pre == NULL) {
            node->next = list;
            return node;
        } else {
            node->next = pre->next;
            pre->next = node;
            return list;
        }
    }
};